Subjects -> MATHEMATICS (Total: 1013 journals)
    - APPLIED MATHEMATICS (92 journals)
    - GEOMETRY AND TOPOLOGY (23 journals)
    - MATHEMATICS (714 journals)
    - MATHEMATICS (GENERAL) (45 journals)
    - NUMERICAL ANALYSIS (26 journals)
    - PROBABILITIES AND MATH STATISTICS (113 journals)

MATHEMATICS (714 journals)                  1 2 3 4 | Last

Showing 1 - 200 of 538 Journals sorted alphabetically
Abakós     Open Access   (Followers: 4)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 2)
Accounting Perspectives     Full-text available via subscription   (Followers: 4)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 13)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 5)
ACM Transactions on Mathematical Software (TOMS)     Hybrid Journal   (Followers: 6)
ACS Applied Materials & Interfaces     Hybrid Journal   (Followers: 43)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 2)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 3)
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: 9)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 6)
Advances in Catalysis     Full-text available via subscription   (Followers: 7)
Advances in Complex Systems     Hybrid Journal   (Followers: 10)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 16)
Advances in Decision Sciences     Open Access   (Followers: 4)
Advances in Difference Equations     Open Access   (Followers: 3)
Advances in Fixed Point Theory     Open Access  
Advances in Geosciences (ADGEO)     Open Access   (Followers: 20)
Advances in Linear Algebra & Matrix Theory     Open Access   (Followers: 6)
Advances in Materials Science     Open Access   (Followers: 21)
Advances in Mathematical Physics     Open Access   (Followers: 6)
Advances in Mathematics     Full-text available via subscription   (Followers: 18)
Advances in Numerical Analysis     Open Access   (Followers: 4)
Advances in Operations Research     Open Access   (Followers: 13)
Advances in Operator Theory     Hybrid Journal  
Advances in Pure Mathematics     Open Access   (Followers: 10)
Advances in Science and Research (ASR)     Open Access   (Followers: 9)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2)
African Journal of Educational Studies in Mathematics and Sciences     Full-text available via subscription   (Followers: 8)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 5)
Afrika Matematika     Hybrid Journal   (Followers: 2)
Air, Soil & Water Research     Open Access   (Followers: 6)
AKSIOMATIK : Jurnal Penelitian Pendidikan dan Pembelajaran Matematika     Open Access  
Al-Jabar : Jurnal Pendidikan Matematika     Open Access  
Al-Qadisiyah Journal for Computer Science and Mathematics     Open Access   (Followers: 3)
AL-Rafidain Journal of Computer Sciences and Mathematics     Open Access   (Followers: 4)
Algebra and Logic     Hybrid Journal   (Followers: 9)
Algebra Colloquium     Hybrid Journal   (Followers: 3)
Algebra Universalis     Hybrid Journal   (Followers: 3)
Algorithmic Operations Research     Open Access   (Followers: 6)
Algorithms     Open Access   (Followers: 14)
Algorithms Research     Open Access   (Followers: 1)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 4)
American Journal of Mathematical Analysis     Open Access   (Followers: 1)
American Journal of Mathematical and Management Sciences     Hybrid Journal  
American Journal of Mathematics     Full-text available via subscription   (Followers: 7)
American Journal of Operations Research     Open Access   (Followers: 6)
American Mathematical Monthly     Full-text available via subscription   (Followers: 3)
An International Journal of Optimization and Control: Theories & Applications     Open Access   (Followers: 12)
Analele Universitatii Ovidius Constanta - Seria Matematica     Open Access  
Analysis and Applications     Hybrid Journal   (Followers: 2)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 7)
Anargya : Jurnal Ilmiah Pendidikan Matematika     Open Access  
Annales Mathematicae Silesianae     Open Access  
Annales mathématiques du Québec     Hybrid Journal   (Followers: 3)
Annales Universitatis Mariae Curie-Sklodowska, sectio A – 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: 15)
Annals of Functional Analysis     Hybrid Journal   (Followers: 2)
Annals of Mathematics     Full-text available via subscription   (Followers: 5)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 13)
Annals of PDE     Hybrid Journal  
Annals of Pure and Applied Logic     Open Access   (Followers: 5)
Annals of the Alexandru Ioan Cuza University - Mathematics     Open Access   (Followers: 1)
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1)
Annals of West University of Timisoara - Mathematics     Open Access   (Followers: 1)
Annals of West University of Timisoara - Mathematics and Computer Science     Open Access   (Followers: 2)
Annuaire du Collège de France     Open Access   (Followers: 6)
ANZIAM Journal     Open Access   (Followers: 1)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 3)
Applications of Mathematics     Hybrid Journal   (Followers: 3)
Applied Categorical Structures     Hybrid Journal   (Followers: 5)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 16)
Applied Mathematics     Open Access   (Followers: 6)
Applied Mathematics     Open Access   (Followers: 6)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 7)
Applied Mathematics - A Journal of Chinese Universities     Hybrid Journal   (Followers: 1)
Applied Mathematics and Nonlinear Sciences     Open Access   (Followers: 1)
Applied Mathematics Letters     Full-text available via subscription   (Followers: 3)
Applied Mathematics Research eXpress     Hybrid Journal   (Followers: 1)
Applied Network Science     Open Access   (Followers: 3)
Applied Numerical Mathematics     Hybrid Journal   (Followers: 4)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 5)
Arab Journal of Mathematical Sciences     Open Access   (Followers: 3)
Arabian Journal of Mathematics     Open Access   (Followers: 1)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 3)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 4)
Archive of Numerical Software     Open Access  
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 5)
Armenian Journal of Mathematics     Open Access  
Arnold Mathematical Journal     Hybrid Journal   (Followers: 1)
Artificial Satellites     Open Access   (Followers: 21)
Asia-Pacific Journal of Operational Research     Hybrid Journal   (Followers: 3)
Asian Journal of Algebra     Open Access   (Followers: 1)
Asian Research Journal of Mathematics     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: 5)
Australian Senior Mathematics Journal     Full-text available via subscription   (Followers: 1)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Axioms     Open Access   (Followers: 1)
Baltic International Yearbook of Cognition, Logic and Communication     Open Access   (Followers: 2)
Banach Journal of Mathematical Analysis     Hybrid Journal  
Basin Research     Hybrid Journal   (Followers: 6)
BIBECHANA     Open Access  
Biomath     Open Access  
BIT Numerical Mathematics     Hybrid Journal  
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  
British Journal for the History of Mathematics     Hybrid Journal   (Followers: 2)
British Journal of Mathematical and Statistical Psychology     Full-text available via subscription   (Followers: 18)
British Journal of Mathematics & Computer Science     Full-text available via subscription   (Followers: 1)
Buletinul Academiei de Stiinte a Republicii Moldova. Matematica     Open Access   (Followers: 2)
Bulletin des Sciences Mathamatiques     Full-text available via subscription   (Followers: 3)
Bulletin of Dnipropetrovsk University. Series : Communications in Mathematical Modeling and Differential Equations Theory     Open Access   (Followers: 3)
Bulletin of Mathematical Sciences     Open Access   (Followers: 1)
Bulletin of Symbolic Logic     Full-text available via subscription   (Followers: 4)
Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics     Open Access  
Bulletin of the Australian Mathematical Society     Full-text available via subscription   (Followers: 2)
Bulletin of the Brazilian Mathematical Society, New Series     Hybrid Journal  
Bulletin of the Iranian Mathematical Society     Hybrid Journal  
Bulletin of the London Mathematical Society     Hybrid Journal   (Followers: 3)
Bulletin of the Malaysian Mathematical Sciences Society     Hybrid Journal  
Cadernos do IME : Série Matemática     Open Access  
Calculus of Variations and Partial Differential Equations     Hybrid Journal   (Followers: 1)
Canadian Journal of Mathematics / Journal canadien de mathématiques     Hybrid Journal  
Canadian Journal of Science, Mathematics and Technology Education     Hybrid Journal   (Followers: 20)
Canadian Mathematical Bulletin     Hybrid Journal  
Carpathian Mathematical Publications     Open Access  
Catalysis in Industry     Hybrid Journal  
CAUCHY     Open Access   (Followers: 1)
CEAS Space Journal     Hybrid Journal   (Followers: 5)
CHANCE     Hybrid Journal   (Followers: 5)
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 1)
Chaos, Solitons & Fractals : X     Open Access   (Followers: 1)
ChemSusChem     Hybrid Journal   (Followers: 8)
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  
Ciencia     Open Access  
CODEE Journal     Open Access  
Cogent Mathematics     Open Access   (Followers: 2)
Cognitive Computation     Hybrid Journal   (Followers: 3)
Collectanea Mathematica     Hybrid Journal  
College Mathematics Journal     Hybrid Journal   (Followers: 3)
COMBINATORICA     Hybrid Journal  
Combinatorics, Probability and Computing     Hybrid Journal   (Followers: 5)
Combustion Theory and Modelling     Hybrid Journal   (Followers: 20)
Commentarii Mathematici Helvetici     Hybrid Journal   (Followers: 1)
Communications in Combinatorics and Optimization     Open Access  
Communications in Contemporary Mathematics     Hybrid Journal  
Communications in Mathematical Physics     Hybrid Journal   (Followers: 3)
Communications On Pure & Applied Mathematics     Hybrid Journal   (Followers: 6)
Complex Analysis and its Synergies     Open Access   (Followers: 1)
Complex Variables and Elliptic Equations: An International Journal     Hybrid Journal  
Compositio Mathematica     Full-text available via subscription   (Followers: 2)
Comptes Rendus : Mathematique     Open Access  
Computational and Applied Mathematics     Hybrid Journal   (Followers: 3)
Computational and Mathematical Methods     Hybrid Journal  
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 2)
Computational Complexity     Hybrid Journal   (Followers: 5)
Computational Mathematics and Modeling     Hybrid Journal   (Followers: 8)
Computational Mechanics     Hybrid Journal   (Followers: 11)
Computational Methods and Function Theory     Hybrid Journal  
Computational Optimization and Applications     Hybrid Journal   (Followers: 9)
Computers & Mathematics with Applications     Full-text available via subscription   (Followers: 10)
Confluentes Mathematici     Hybrid Journal  
Constructive Mathematical Analysis     Open Access  
Contributions to Discrete Mathematics     Open Access  
Contributions to Game Theory and Management     Open Access  
COSMOS     Hybrid Journal   (Followers: 1)
Cross Section     Full-text available via subscription   (Followers: 1)
Cryptography and Communications     Hybrid Journal   (Followers: 11)
Cuadernos de Investigación y Formación en Educación Matemática     Open Access  
Cubo. A Mathematical Journal     Open Access  
Current Research in Biostatistics     Open Access   (Followers: 8)
Czechoslovak Mathematical Journal     Hybrid Journal  
Daya Matematis : Jurnal Inovasi Pendidikan Matematika     Open Access  
Demographic Research     Open Access   (Followers: 14)
Design Journal : An International Journal for All Aspects of Design     Hybrid Journal   (Followers: 35)
Desimal : Jurnal Matematika     Open Access  
Dhaka University Journal of Science     Open Access  
Differential Equations and Dynamical Systems     Hybrid Journal   (Followers: 2)
Differentsial'nye Uravneniya     Open Access  
Digital Experiences in Mathematics Education     Hybrid Journal   (Followers: 3)
Discrete Mathematics     Hybrid Journal   (Followers: 7)
Discrete Mathematics & Theoretical Computer Science     Open Access   (Followers: 1)
Discrete Mathematics, Algorithms and Applications     Hybrid Journal   (Followers: 2)
Discussiones Mathematicae - General Algebra and Applications     Open Access  
Discussiones Mathematicae Graph Theory     Open Access   (Followers: 1)
Diskretnaya Matematika     Full-text available via subscription  
Doklady Akademii Nauk     Open Access  

        1 2 3 4 | Last

Similar Journals
Journal Cover
Computational Complexity
Journal Prestige (SJR): 0.381
Citation Impact (citeScore): 1
Number of Followers: 5  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1420-8954 - ISSN (Online) 1016-3328
Published by Springer-Verlag Homepage  [2467 journals]
  • On sets of linear forms of maximal complexity

    • Free pre-print version: Loading...

      Abstract: Abstract We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n – 1) additions.
      PubDate: 2022-11-29
       
  • Quantum versus Randomized Communication Complexity, with Efficient Players

    • Free pre-print version: Loading...

      Abstract: Abstract We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N, such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where at the beginning of the protocol Alice and Bob also have polylog(N) entangled EPR pairs). Any classical randomized protocol for f, with any number of rounds, has communication complexity at least \(\tilde{\Omega}\left(N^{1/4}\right)\) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog(N) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of \(\Omega\left(N^{1/2}\right)\) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
      PubDate: 2022-10-28
       
  • On Hitting-Set Generators for Polynomials that Vanish Rarely

    • Free pre-print version: Loading...

      Abstract: Abstract The problem of constructing pseudorandom generators for polynomials of low degree is fundamental in complexity theory and has numerous well-known applications. We study the following question, which is a relaxation of this problem: Is it easier to construct pseudorandom generators, or even hitting-set generators, for polynomials \(p:\mathbb{F}^n\rightarrow\mathbb{F}\) of degree d if we are guaranteed that the polynomial vanishes on at most an \(\varepsilon > 0\) fraction of its inputs' We will specifically be interested in tiny values of \(\varepsilon\ll d/ F \) . This question was first considered by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for a particular application, and another specific setting was later studied by the third author (CCC 2017). In this work, our main interest is a systematic study of the relaxed problem,in its general form, and we prove results that significantly improve and extend the two previously known results. Our contributions are of two types: \( \circ \) Over fields of size \(2\le \mathbb{F} \le\mathrm{poly}(n)\) we show that the seed length of any hitting-set generator for polynomials of degree \(d\le n^{.49}\) that vanish on at most \(\varepsilon= \mathbb{F} ^{-t}\) of their inputs is at least \(\Omega\left((d/t)\cdot\log(n)\right)\) . \( \circ \) Over \(\mathbb{F}_2\) , we show that there exists a (non-explicit) hitting-set generator for polynomials of degree \(d\le n^{.99}\) that vanish on at most \(\varepsilon= \mathbb{F} ^{-t}\) of their inputs with seed length \(O\left((d-t)\cdot\log(n)\right)\) . We also show a polynomial-time computable hitting-set generator with seed length \(O\left( (d-t)\cdot\left(2^{d-t}+\log(n)\right) \right)\) . In addition, we prove that the problem we study is closely related to the following question: “Does there exist a small set \(S\subseteq\mathbb{F}^n\) whose degree-d closure is very large'”, where the degree-d closure of S is the variety induced by the set of degree-d polynomials that vanish on S.
      PubDate: 2022-10-22
       
  • Improved Hitting Set for Orbit of ROABPs

    • Free pre-print version: Loading...

      Abstract: Abstract The orbit of an n-variate polynomial \(f({\rm x})\) over a field \(\mathbb{F}\) is the set \(\{f(A{\rm x} + {\rm b})\,\mid\, A\in{\rm GL}(n, \mathbb{F})\mbox{ and }{\rm b}\in \mathbb{F}^n\}\) , and the orbit of a polynomial class is the union of orbits of the polynomials in it. In this paper, we give improved constructions of hitting sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than \(d\) , we construct a hitting set of size \((ndw)^{O(w^2\log n\cdot \min\{w^2, d\log w\})}\) for the orbit of ROABPs in unknown variable order where \(d\) is the individual degree and \(w\) is the width of ROABPs. We also give a hitting set of size \((ndw)^{O(\min\{w^2,d\log w\})}\) for the orbit of polynomials computed by width-w ROABPs in any variable order. Our hitting sets improve upon the results of Saha & Thankey (2021) who gave an \((ndw)^{O(d\log w)}\) size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and \((nw)^{O(w^6\log n)}\) size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance \(d>n\) , was asked as an open problem by Saha & Thankey (2021) and this work solves it in small width setting. We prove some new rank concentration results by establishing low-cone concentration for polynomials over vector spaces, and they strengthen some previously known low-support-based rank concentration results shown in Forbes et al. (2013). These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets.
      PubDate: 2022-10-12
       
  • The Complexity of Finding Fair Independent Sets in Cycles

    • Free pre-print version: Loading...

      Abstract: Abstract Let G be a cycle graph and let \(V_1,\ldots,V_m\) be a partition of its vertex set into m sets. An independent set S of G is said to fairly represent the partition if \( S \cap V_i \geq \frac{1}{2} \cdot V_i -1\) for all \(i \in [m]\) . It is known that for every cycle and every partition of its vertex set, there exists an independent set that fairly represents the partition (Aharoni et al. 2017). We prove that the problem of finding such an independent set is PPA-complete. As an application, we show that the problem of finding a monochromatic edge in a Schrijver graph, given a succinct representation of a coloring that uses fewer colors than its chromatic number, is PPA-complete as well. The work is motivated by the computational aspects of the `cycle plus triangles' problem and of its extensions.
      PubDate: 2022-10-11
       
  • Quantum generalizations of the polynomial hierarchy with applications to
           QMA(2)

    • Free pre-print version: Loading...

      Abstract: Abstract The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, \(\rm{QCPH}\) , uses classical proofs, and the second, \(\rm{QPH}\) , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, \(\rm{Q\Sigma_3}\) , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for \(\rm{QMA(2)}\) , the variant of Quantum Merlin-Arthur ( \(\rm{QMA}\) ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if \(\rm{QCPH = QPH}\) (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in \(Po^{pp^{pp}}\) ). Second, because \(\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}\) , \(\rm{QMA(2)}\) is strictly contained in NEXP unless \(\rm{QMA(2)}=\rm{Q\Sigma_3}\) (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').
      PubDate: 2022-09-20
      DOI: 10.1007/s00037-022-00231-8
       
  • A Lower Bound on Determinantal Complexity

    • Free pre-print version: Loading...

      Abstract: Abstract The determinantal complexity of a polynomial \(P \in \mathbb{F}[x_1, \ldots, x_n]\) over a field \(\mathbb{F}\) is the dimension of the smallest matrix M whose entries are affine functions in \(\mathbb{F}[x_1, \ldots, x_n]\) such that \(P = {\rm Det}(M)\) . We prove that the determinantal complexity of the polynomial \(\sum_{i = 1}^n x_i^n\) is at least \(1.5n - 3\) . For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long-standing open problem to prove a lower bound which is super linear in \(\max\{n,d\}\) . Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than \(\max\{n,d\}\) , and improves upon the prior best bound of \(n + 1\) , proved by Alper et al. (2017) for the same polynomial.
      PubDate: 2022-09-19
      DOI: 10.1007/s00037-022-00228-3
       
  • Zeros and approximations of Holant polynomials on the complex plane

    • Free pre-print version: Loading...

      Abstract: We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
      PubDate: 2022-07-27
      DOI: 10.1007/s00037-022-00226-5
       
  • A cost-scaling algorithm for computing the degree of determinants

    • Free pre-print version: Loading...

      Abstract: Abstract In this paper, we address computation of the degree \(\deg {\rm Det} A\) of Dieudonné determinant \({\rm Det} A\) of $$\begin{aligned} A = \sum_{k=1}^m A_k x_k t^{c_k}, \end{aligned}$$ where \(A_k\) are \(n \times n\) matrices over a field \(\mathbb{K}\) , \(x_k\) are noncommutative variables, t is a variable commuting with \(x_k\) , \(c_k\) are integers, and the degree is considered for t. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that \(\deg {\rm Det} A\) is obtained by a discrete convex optimization on a Euclidean building (Hirai 2019). We extend this framework by incorporating a cost-scaling technique and show that \(\deg {\rm Det} A\) can be computed in time polynomial of \(n,m,\log_2 C\) , where \(C:= \max_k c_k \) . We give a polyhedral interpretation of \(\deg {\rm Det}\) , which says that \(\deg {\rm Det}\) A is given by linear optimization over an integral polytope with respect to objective vector \(c = (c_k)\) . Based on it, we show that our algorithm becomes a strongly polynomial one. We also apply our result to an algebraic combinatorial optimization problem arising from a symbolic matrix having \(2 \times 2\) -submatrix structure.
      PubDate: 2022-07-23
      DOI: 10.1007/s00037-022-00227-4
       
  • Disjointness through the Lens of Vapnik–Chervonenkis Dimension:
           Sparsity and Beyond

    • Free pre-print version: Loading...

      Abstract: Abstract The disjointness problem—where Alice and Bob are given two subsets of \(\{1, \dots, n\}\) and they have to check if their sets intersect—is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be \(\Theta(n)\) , it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik—Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by d, we analyze how large can the deterministic and randomized communication complexities be, as a function of d and n. The d-sparse set disjointness problem, where the sets have size at most d, is one such set system with VC dimension d. The deterministic and the randomized communication complexities of the d-sparse set disjointness problem have been well studied and are known to be \(\Theta \left( d \log \left({n}/{d}\right)\right)\) and \(\Theta(d)\) , respectively, in the multi-round communication setting. In this paper, we address the question of whether the randomized communication complexity of the disjointness problem is always upper bounded by a function of the VC dimension of the set system, and does there always exist a gap between the deterministic and randomized communication complexities of the disjointness problem for set systems with small VC dimension. We construct two natural set systems of VC dimension d, motivated from geometry. Using these set systems, we show that the deterministic and randomized communication complexity can be \(\widetilde{\Theta}\left(d\log \left( n/d \right)\right)\) for set systems of VC dimension d and this matches the deterministic upper bound for all set systems of VC dimension d. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exist set systems of VC dimension d such that both deterministic and randomized (one-way and multi-round) complexities for the set intersection problem can be as high as \(\Theta\left( d\log \left( n/d \right) \right)\) .
      PubDate: 2022-07-05
      DOI: 10.1007/s00037-022-00225-6
       
  • Quadratic Lower Bounds for Algebraic Branching Programs and Formulas

    • Free pre-print version: Loading...

      Abstract: Abstract We show that any Algebraic Branching Program (ABP) computing the polynomial \(\sum _{i = 1}^n x_i^n\) has at least \(\Omega (n^2)\) vertices. This improves upon the lower bound of \(\Omega (n\log n)\) , which follows from the classical result of Strassen (1973a) and Baur & Strassen (1983), and extends the results in Kumar (2019), which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial. Our proof relies on a notion of depth reduction, which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial \(\sum _{i=1}^n x_i^n\) can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial \(\sum _{i = 1}^n x_i^n + \varepsilon ({\bf x})\) , for a structured “error polynomial” \(\varepsilon ({\bf x})\) . To complete the proof, we then observe that the lower bound in Kumar (2019) is robust enough and continues to hold for all polynomials \(\sum _{i = 1}^n x_i^n + \varepsilon ({\bf x})\) , where \(\varepsilon ({\bf x})\) has the appropriate structure. We also use our ideas to show an \(\Omega (n^2)\) lower bound of the size of algebraic formulas computing the elementary symmetric polynomial of degree 0.1n on n variables. This is a slight improvement upon the prior best known formula lower bound (proved for a different polynomial) of \(\Omega (n^2/\log n)\) Kalorkoti (1985); Nechiporuk (1966); Shpilka & Yehudayoff (2010). Interestingly, this lower bound is asymptotically better than \(n^2/\log n\) , the strongest lower bound that can be proved using previous methods. This lower bound also matches the upper bound, due to Ben-Or, who showed that elementary symmetric polynomials can be computed by algebraic formula (in fact depth-3 formula) of size \(O(n^2)\) . Prior to this work, Ben-Or’s construction was known to be optimal only for algebraic formulas of depth-3 (Shpilka & Wigderson 2001).
      PubDate: 2022-07-05
      DOI: 10.1007/s00037-022-00223-8
       
  • Improved bounds on the AN-complexity of $$O(1)$$ O ( 1 ) -linear functions

    • Free pre-print version: Loading...

      Abstract: Abstract We consider arithmetic circuits with arbitrary gates for computing Boolean functions that are represented by low-degree polynomials over GF(2). An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number. This model and the corresponding complexity measure, called AN-complexity, were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), and it is meaningful only for low-degree polynomials (where the arity of a gate is not due to the degree of the polynomial that the gate computes but rather to the number of variables in it). The AN-complexity of a function yields an upper bound on the size of depth-three Boolean circuits for computing the function. Specifically, the depth-three size of Boolean circuits is at most exponential in the AN-complexity of the function. Hence, proving linear lower bounds on the AN-complexity of explicit O(1)-linear functions is an essential step toward proving that depth-three Boolean circuits for these functions require exponential size. In this work, we present explicit O(1)-linear functions that require depth-two arithmetic circuits of almost linear AN-complexity. Specifically, for every \(\epsilon > 0\) , we show an explicit poly \(({1/ \epsilon})\) -linear function \(f:\{0,1\}^{\mathrm{poly} (1/\epsilon)\cdot n}\to \{0,1\}\) such that any depth-two arithmetic circuit that computes f must use gates of arity at least \(n^{1-\epsilon}\) . In particular, for every \(\epsilon > 0\) and \(t=O(1/\epsilon^2)\) , the \(\Omega(n^{1-\epsilon})\) lower bound holds also for the t-linear function $$\begin{aligned}f(x^{(1)},x^{(2)},...,x^{(t)}) = \sum_{i_1,...,i_{t-1}\in[n]} \left(\prod_{j\in[t-1]} x^{(j)}_{i_{j}}\right) \cdot x^{(t)}_{{i_1+i_2+\cdots+i_{t-1}}} \end{aligned}$$ This improves over a corresponding lower bound of \(\tilde \Omega(n^{2/3})\) that was known for an explicit trilinear function (Goldreich and Tal, Computational Complexity, 2018), but leaves open the problem of showing similar AN-complexity lower bounds for arithmetic circuits of larger depth. A key aspect in our proof is considering many (extremely skewed) random restrictions, and contrasting the sum of the values of the original function and the circuit (which supposedly computes it) taken over a (carefully chosen) subset of these random restrictions. We show that if the original circuit has too low AN-complexity, then these two sums cannot be equal, which yields a contradiction.
      PubDate: 2022-06-23
      DOI: 10.1007/s00037-022-00224-7
       
  • A quasi-linear irreducibility test in $$\mathbb{K}[[x]][y]$$ K [ [ x ] ] [
           y ]

    • Free pre-print version: Loading...

      Abstract: Abstract We provide an irreducibility test in the ring \(\mathbb{K}[[x]][y]\) whose complexity is quasi-linear with respect to the discriminant valuation, assuming the input polynomial \(F\) is square-free and \(\mathbb{K}\) is a perfect field of characteristic not dividing \(\deg(F)\) . The algorithm uses the theory of approximate roots and may be seen as a generalisation of Abhyankar's irreducibility criterion to the case of non-algebraically closed residue fields.
      PubDate: 2022-06-11
      DOI: 10.1007/s00037-022-00221-w
       
  • Computing zero-dimensional tropical varieties via projections

    • Free pre-print version: Loading...

      Abstract: Abstract We present an algorithm for computing zero-dimensional tropical varieties using projections. Our main tools are fast monomial transforms of triangular sets. Given a Gröbner basis, we prove that our algorithm requires only a polynomial number of arithmetic operations, and, for ideals in shape position, we show that its timings compare well against univariate factorization and backsubstitution. We conclude that the complexity of computing positive-dimensional tropical varieties via a traversal of the Gröbner complex is dominated by the complexity of the Gröbner walk.
      PubDate: 2022-05-20
      DOI: 10.1007/s00037-022-00222-9
       
  • Expander-Based Cryptography Meets Natural Proofs

    • Free pre-print version: Loading...

      Abstract: Abstract We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich’s pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander’s neighbor function and/or of the local predicate. Our two key conceptual contributions are: We put forward the possibility that the choice of expander matters in expander-based cryptography. In particular, using expanders whose neighbor function has low circuit complexity might compromise the security of Goldreich’s PRG and OWF in certain settings. We show that the security of Goldreich’s PRG and OWF over arbitrary expanders is closely related to two other long-standing problems: The existence of unbalanced lossless expanders with low-complexity neighbor function, and limitations on circuit lower bounds (i.e., natural proofs). In particular, our results further motivate the investigation of affine/local unbalanced lossless expanders and of average-case lower bounds against DNF-XOR circuits. We prove two types of technical results. First, in the regime of quasipolynomial stretch (in which the output length of the PRG and the running time of the distinguisher are quasipolynomial in the seed length) we unconditionally break Goldreich’s PRG, when instantiated with a specific expander whose existence we prove, and for a class of predicates that match the parameters of the currently-best “hard” candidates. Secondly, conditioned on the existence of expanders whose neighbor functions have extremely low circuit complexity, we present attacks on Goldreich’s PRG in the regime of polynomial stretch. As one corollary, conditioned on the existence of the foregoing expanders, we show that either the parameters of natural properties for several constant-depth circuit classes cannot be improved, even mildly; or Goldreich’s PRG is insecure in the regime of a large polynomial stretch for some expander graphs, regardless of the predicate used.
      PubDate: 2022-03-16
      DOI: 10.1007/s00037-022-00220-x
       
  • Amplification with One NP Oracle Query

    • Free pre-print version: Loading...

      Abstract: Abstract We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, onesided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our inclusions are tight for relativizing techniques.
      PubDate: 2022-02-05
      DOI: 10.1007/s00037-021-00219-w
       
  • The complexity of approximating the complex-valued Potts model

    • Free pre-print version: Loading...

      Abstract: Abstract We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q \(\geq\) 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.
      PubDate: 2022-02-03
      DOI: 10.1007/s00037-021-00218-x
       
  • Rank and border rank of Kronecker powers of tensors and Strassen's laser
           method

    • Free pre-print version: Loading...

      Abstract: Abstract We prove that the border rank of the Kronecker square of the little Coppersmith–Winograd tensor \(T_{cw,q}\) is the square of its border rank for \(q > 2\) and that the border rank of its Kronecker cube is the cube of its border rank for \(q > 4\) . This answers questions raised implicitly by Coppersmith & Winograd (1990, §11) and explicitly by Bläser (2013, Problem 9.8) and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith–Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen's laser method, introducing a skew-symmetric version of the Coppersmith–Winograd tensor, \(T_{skewcw,q}\) . For \(q = 2\) , the Kronecker square of this tensor coincides with the \(3\times 3\) determinant polynomial, \(\det_{3} \in \mathbb{C}^{9} \otimes \mathbb{C}^{9} \otimes \mathbb{C}^{9}\) , regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of \(\det_3\) , exhibiting a strict submultiplicative behaviour for \(T_{skewcw,2}\) which is promising for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in \(\mathbb{C}^{3} \otimes \mathbb{C}^{3} \otimes \mathbb{C}^{3}\) .
      PubDate: 2021-12-18
      DOI: 10.1007/s00037-021-00217-y
       
  • Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations
           of Tseitin Formulas for All Constant-Degree Graphs

    • Free pre-print version: Loading...

      PubDate: 2021-11-17
      DOI: 10.1007/s00037-021-00216-z
       
  • Factorization of Polynomials Given by Arithmetic Branching Programs

    • Free pre-print version: Loading...

      Abstract: Abstract Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly \( (s^{ {\rm \log} s}) \) .
      PubDate: 2021-10-15
      DOI: 10.1007/s00037-021-00215-0
       
 
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
 


Your IP address: 3.225.221.130
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-