8 Search Results for "Babai, L�szl�"


Document
Matrix Rigidity Depends on the Target Field

Authors: László Babai and Bohdan Kivva

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r (Valiant, 1977). We study the dependence of rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity"). We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of 3/2-o(1) between strict and absolute rigidities. The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments. Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over 𝔽₂.

Cite as

László Babai and Bohdan Kivva. Matrix Rigidity Depends on the Target Field. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 41:1-41:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.CCC.2021.41,
  author =	{Babai, L\'{a}szl\'{o} and Kivva, Bohdan},
  title =	{{Matrix Rigidity Depends on the Target Field}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{41:1--41:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.41},
  URN =		{urn:nbn:de:0030-drops-143153},
  doi =		{10.4230/LIPIcs.CCC.2021.41},
  annote =	{Keywords: Matrix rigidity, field extension}
}
Document
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

Authors: Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can be embedded in the n-clique K_n, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group G⊑ 𝕊_n can be upper bounded by three structural parameters of connected graphs embedding G: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group G ⊑ 𝕊_n that can be embedded into a connected graph with m vertices, treewidth k, and maximum degree Δ, can also be generated by a context-free grammar of size 2^{O(kΔlogΔ)}⋅ m^{O(k)}. By combining our upper bound with a connection established by Pesant, Quimper, Rousseau and Sellmann [Gilles Pesant et al., 2009] between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity 2^{O(kΔlogΔ)}⋅ m^{O(k)}. The above upper bounds can be used to provide trade-offs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated 2^{Ω(n)} lower bound on the grammar complexity of the symmetric group 𝕊_n due to Glaister and Shallit [Glaister and Shallit, 1996] we have that connected graphs of treewidth o(n/log n) and maximum degree o(n/log n) embedding subgroups of 𝕊_n of index 2^{cn} for some small constant c must have n^{ω(1)} vertices. This lower bound can be improved to exponential on graphs of treewidth n^{ε} for ε < 1 and maximum degree o(n/log n).

Cite as

Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2020.50,
  author =	{Jaffke, Lars and de Oliveira Oliveira, Mateus and Tiwary, Hans Raj},
  title =	{{Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.50},
  URN =		{urn:nbn:de:0030-drops-127161},
  doi =		{10.4230/LIPIcs.MFCS.2020.50},
  annote =	{Keywords: Permutation Groups, Context Free Grammars, Extension Complexity, Graph Embedding Complexity}
}
Document
Track A: Algorithms, Complexity and Games
Determinant Equivalence Test over Finite Fields and over Q

Authors: Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
The determinant polynomial Det_n(x) of degree n is the determinant of a n x n matrix of formal variables. A polynomial f is equivalent to Det_n(x) over a field F if there exists a A in GL(n^2,F) such that f = Det_n(A * x). Determinant equivalence test over F is the following algorithmic task: Given black-box access to a f in F[x], check if f is equivalent to Det_n(x) over F, and if so then output a transformation matrix A in GL(n^2,F). In (Kayal, STOC 2012), a randomized polynomial time determinant equivalence test was given over F = C. But, to our knowledge, the complexity of the problem over finite fields and over Q was not well understood. In this work, we give a randomized poly(n,log |F|) time determinant equivalence test over finite fields F (under mild restrictions on the characteristic and size of F). Over Q, we give an efficient randomized reduction from factoring square-free integers to determinant equivalence test for quadratic forms (i.e. the n=2 case), assuming GRH. This shows that designing a polynomial-time determinant equivalence test over Q is a challenging task. Nevertheless, we show that determinant equivalence test over Q is decidable: For bounded n, there is a randomized polynomial-time determinant equivalence test over Q with access to an oracle for integer factoring. Moreover, for any n, there is a randomized polynomial-time algorithm that takes input black-box access to a f in Q[x] and if f is equivalent to Det_n over Q then it returns a A in GL(n^2,L) such that f = Det_n(A * x), where L is an extension field of Q and [L : Q] <= n. The above algorithms over finite fields and over Q are obtained by giving a polynomial-time randomized reduction from determinant equivalence test to another problem, namely the full matrix algebra isomorphism problem. We also show a reduction in the converse direction which is efficient if n is bounded. These reductions, which hold over any F (under mild restrictions on the characteristic and size of F), establish a close connection between the complexity of the two problems. This then leads to our results via applications of known results on the full algebra isomorphism problem over finite fields (Rónyai, STOC 1987 and Rónyai, J. Symb. Comput. 1990) and over Q (Ivanyos {et al}., Journal of Algebra 2012 and Babai {et al}., Mathematics of Computation 1990).

Cite as

Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant Equivalence Test over Finite Fields and over Q. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ICALP.2019.62,
  author =	{Garg, Ankit and Gupta, Nikhil and Kayal, Neeraj and Saha, Chandan},
  title =	{{Determinant Equivalence Test over Finite Fields and over Q}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.62},
  URN =		{urn:nbn:de:0030-drops-106382},
  doi =		{10.4230/LIPIcs.ICALP.2019.62},
  annote =	{Keywords: Determinant equivalence test, full matrix algebra isomorphism, Lie algebra}
}
Document
List-Decoding Homomorphism Codes with Arbitrary Codomains

Authors: László Babai, Timothy J. F. Black, and Angela Wuu

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)


Abstract
The codewords of the homomorphism code aHom(G,H) are the affine homomorphisms between two finite groups, G and H, generalizing Hadamard codes. Following the work of Goldreich-Levin (1989), Grigorescu et al. (2006), Dinur et al. (2008), and Guo and Sudan (2014), we further expand the range of groups for which local list-decoding is possible up to mindist, the minimum distance of the code. In particular, for the first time, we do not require either G or H to be solvable. Specifically, we demonstrate a poly(1/epsilon) bound on the list size, i. e., on the number of codewords within distance (mindist-epsilon) from any received word, when G is either abelian or an alternating group, and H is an arbitrary (finite or infinite) group. We conjecture that a similar bound holds for all finite simple groups as domains; the alternating groups serve as the first test case. The abelian vs. arbitrary result permits us to adapt previous techniques to obtain efficient local list-decoding for this case. We also obtain efficient local list-decoding for the permutation representations of alternating groups (the codomain is a symmetric group) under the restriction that the domain G=A_n is paired with codomain H=S_m satisfying m < 2^{n-1}/sqrt{n}. The limitations on the codomain in the latter case arise from severe technical difficulties stemming from the need to solve the homomorphism extension (HomExt) problem in certain cases; these are addressed in a separate paper (Wuu 2018). We introduce an intermediate "semi-algorithmic" model we call Certificate List-Decoding that bypasses the HomExt bottleneck and works in the alternating vs. arbitrary setting. A certificate list-decoder produces partial homomorphisms that uniquely extend to the homomorphisms in the list. A homomorphism extender applied to a list of certificates yields the desired list.

Cite as

László Babai, Timothy J. F. Black, and Angela Wuu. List-Decoding Homomorphism Codes with Arbitrary Codomains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.APPROX-RANDOM.2018.29,
  author =	{Babai, L\'{a}szl\'{o} and Black, Timothy J. F. and Wuu, Angela},
  title =	{{List-Decoding Homomorphism Codes with Arbitrary Codomains}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.29},
  URN =		{urn:nbn:de:0030-drops-94338},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.29},
  annote =	{Keywords: Error-correcting codes, Local algorithms, Local list-decoding, Finite groups, Homomorphism codes}
}
Document
A Hierarchy Theorem for Interactive Proofs of Proximity

Authors: Tom Gur and Ron D. Rothblum

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)


Abstract
The number of rounds, or round complexity, used in an interactive protocol is a fundamental resource. In this work we consider the significance of round complexity in the context of Interactive Proofs of Proximity (IPPs). Roughly speaking, IPPs are interactive proofs in which the verifier runs in sublinear time and is only required to reject inputs that are far from the language. Our main result is a round hierarchy theorem for IPPs, showing that the power of IPPs grows with the number of rounds. More specifically, we show that there exists a gap function g(r) = Theta(r^2) such that for every constant r \geq 1 there exists a language that (1) has a g(r)-round IPP with verification time t=t(n,r) but (2) does not have an r-round IPP with verification time t (or even verification time t'=\poly(t)). In fact, we prove a stronger result by exhibiting a single language L such that, for every constant r \geq 1, there is an O(r^2)-round IPP for L with t=n^{O(1/r)} verification time, whereas the verifier in any r-round IPP for L must run in time at least t^{100}. Moreover, we show an IPP for L with a poly-logarithmic number of rounds and only poly-logarithmic erification time, yielding a sub-exponential separation between the power of constant-round IPPs versus general (unbounded round) IPPs. From our hierarchy theorem we also derive implications to standard interactive proofs (in which the verifier can run in polynomial time). Specifically, we show that the round reduction technique of Babai and Moran (JCSS, 1988) is (almost) optimal among all blackbox transformations, and we show a connection to the algebrization framework of Aaronson and Wigderson (TOCT, 2009).

Cite as

Tom Gur and Ron D. Rothblum. A Hierarchy Theorem for Interactive Proofs of Proximity. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 39:1-39:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{gur_et_al:LIPIcs.ITCS.2017.39,
  author =	{Gur, Tom and Rothblum, Ron D.},
  title =	{{A Hierarchy Theorem for Interactive Proofs of Proximity}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{39:1--39:43},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.39},
  URN =		{urn:nbn:de:0030-drops-81536},
  doi =		{10.4230/LIPIcs.ITCS.2017.39},
  annote =	{Keywords: Complexity Theory, Property Testing, Interactive Proofs}
}
Document
The Graph Isomorphism Problem (Dagstuhl Seminar 15511)

Authors: László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán

Published in: Dagstuhl Reports, Volume 5, Issue 12 (2016)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15511 "The Graph Isomorphism Problem". The goal of the seminar was to bring together researchers working on the numerous topics closely related to the Isomorphism Problem to foster their collaboration. To this end the participants of the seminar included researchers working on the theoretical and practical aspects of isomorphism ranging from the fields of algorithmic group theory, finite model theory, combinatorial optimization to algorithmics. A highlight of the conference was the presentation of a new quasi-polynomial time algorithm for the Graph Isomorphism Problem, providing the first improvement since 1983.

Cite as

László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán. The Graph Isomorphism Problem (Dagstuhl Seminar 15511). In Dagstuhl Reports, Volume 5, Issue 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{babai_et_al:DagRep.5.12.1,
  author =	{Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo},
  title =	{{The Graph Isomorphism Problem (Dagstuhl Seminar 15511)}},
  pages =	{1--17},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{12},
  editor =	{Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.12.1},
  URN =		{urn:nbn:de:0030-drops-58028},
  doi =		{10.4230/DagRep.5.12.1},
  annote =	{Keywords: canonical forms, complexity, computational group theory, graph isomorphism}
}
Document
Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers

Authors: László Babai and Youming Qiao

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)


Abstract
We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n^{log n} bound on the time complexity for the general case has not been improved over the past four decades. Recently, Babai et al. (following Babai et al. in SODA 2011) presented a polynomial-time algorithm for groups without abelian normal subgroups, which suggests solvable groups as the hard case for group isomorphism problem. Extending recent work by Le Gall (STACS 2009) and Qiao et al. (STACS 2011), in this paper we design a polynomial-time algorithm to test isomorphism for the largest class of solvable groups yet, namely groups with abelian Sylow towers, defined as follows. A group G is said to possess a Sylow tower, if there exists a normal series where each quotient is isomorphic to Sylow subgroup of G. A group has an abelian Sylow tower if it has a Sylow tower and all its Sylow subgroups are abelian. In fact, we are able to compute the coset of isomorphisms of groups formed as coprime extensions of an abelian group, by a group whose automorphism group is known. The mathematical tools required include representation theory, Wedderburn's theorem on semisimple algebras, and M.E. Harris's 1980 work on p'-automorphisms of abelian p-groups. We use tools from the theory of permutation group algorithms, and develop an algorithm for a parameterized versin of the graph-isomorphism-hard setwise stabilizer problem, which may be of independent interest.

Cite as

László Babai and Youming Qiao. Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 453-464, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.STACS.2012.453,
  author =	{Babai, L\'{a}szl\'{o} and Qiao, Youming},
  title =	{{Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{453--464},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.453},
  URN =		{urn:nbn:de:0030-drops-34008},
  doi =		{10.4230/LIPIcs.STACS.2012.453},
  annote =	{Keywords: polynomial-time algorithm, group isomorphism, solvable group}
}
Document
Evasiveness and the Distribution of Prime Numbers

Authors: László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
A Boolean function on $N$ variables is called \emph{evasive} if its decision-tree complexity is $N$. A sequence $B_n$ of Boolean functions is \emph{eventually evasive} if $B_n$ is evasive for all sufficiently large $n$. We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, ``forbidden subgraph $H$'' is eventually evasive and (b) all nontrivial monotone properties of graphs with $\le n^{3/2-\epsilon}$ edges are eventually evasive. ($n$ is the number of vertices.) While Chowla's conjecture is not known to follow from the Extended Riemann Hypothesis (ERH, the Riemann Hypothesis for Dirichlet's $L$ functions), we show (b) with the bound $O(n^{5/4-\epsilon})$ under ERH. We also prove unconditional results: (a$'$) for any graph $H$, the query complexity of ``forbidden subgraph $H$'' is $\binom{n}{2} - O(1)$; (b$'$) for some constant $c>0$, all nontrivial monotone properties of graphs with $\le cn\log n+O(1)$ edges are eventually evasive. Even these weaker, unconditional results rely on deep results from number theory such as Vinogradov's theorem on the Goldbach conjecture. Our technical contribution consists in connecting the topological framework of Kahn, Saks, and Sturtevant (1984), as further developed by Chakrabarti, Khot, and Shi (2002), with a deeper analysis of the orbital structure of permutation groups and their connection to the distribution of prime numbers. Our unconditional results include stronger versions and generalizations of some result of Chakrabarti et al.

Cite as

László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik. Evasiveness and the Distribution of Prime Numbers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.STACS.2010.2445,
  author =	{Babai, L\'{a}szl\'{o} and Banerjee, Anandam and Kulkarni, Raghav and Naik, Vipul},
  title =	{{Evasiveness and the Distribution of Prime Numbers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{71--82},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2445},
  URN =		{urn:nbn:de:0030-drops-24451},
  doi =		{10.4230/LIPIcs.STACS.2010.2445},
  annote =	{Keywords: Decision tree complexity, evasiveness, graph property, group action, Dirichlet primes, Extended Riemann Hypothesis}
}
  • Refine by Author
  • 5 Babai, László
  • 1 Banerjee, Anandam
  • 1 Black, Timothy J. F.
  • 1 Dawar, Anuj
  • 1 Garg, Ankit
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Coding theory
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Algebraic language theory
  • Show More...

  • Refine by Keyword
  • 1 Complexity Theory
  • 1 Context Free Grammars
  • 1 Decision tree complexity
  • 1 Determinant equivalence test
  • 1 Dirichlet primes
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 1 2010
  • 1 2012
  • 1 2016
  • 1 2017
  • 1 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail