Count-free Weisfeiler-Leman and group isomorphism. (English) Zbl 07854824
Reviewer: Igor Subbotin (Los Angeles)
Found 66 Documents (Results 1–66)
Computational complexity of normalizing constants for the product of determinantal point processes. (English) Zbl 1541.68157
On the parallel complexity of group isomorphism via Weisfeiler-Leman. (English) Zbl 07856022
Fernau, Henning (ed.) et al., Fundamentals of computation theory. 24th international symposium, FCT 2023, Trier, Germany, September 18–21, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14292, 234-247 (2023).
MSC:
68Qxx
Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields. (English) Zbl 1498.11241
A linear-algebraic and lattice-theoretical look at the Cleaning Lemma of quantum coding theory. (English) Zbl 07553074
On a fast algorithm for computing the Fourier transform. (English. Russian original) Zbl 1522.65268
Mosc. Univ. Math. Bull. 76, No. 3, 123-128 (2021); translation from Vestn. Mosk. Univ., Ser. I 76, No. 3, 36-41 (2021).
MSC:
65T50
Integer multiplication in time \(O(n\log n)\). (English) Zbl 1480.11162
Reviewer: Armen Bagdasaryan (Madīnat al-Kuwait)
Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial. (English) Zbl 1512.68482
Computational complexity of computing symmetries in finite-domain planning. (English) Zbl 1512.68313
Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates. (Russian. English summary) Zbl 1491.68090
Multiplication. (Russian. English summary) Zbl 1455.68294
Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth. (English) Zbl 1433.68141
MSC:
68Q06
Runtime analysis of discrete particle swarm optimization applied to shortest paths computation. (English) Zbl 1525.68213
Liefooghe, Arnaud (ed.) et al., Evolutionary computation in combinatorial optimization. 19th European conference, EvoCOP 2019, held as part of EvoStar 2019, Leipzig, Germany, April 24–26, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11452, 115-130 (2019).
Faster integer multiplication using short lattice vectors. (English) Zbl 07721131
Scheidler, Renate (ed.) et al., ANTS XIII. Proceedings of the thirteenth algorithmic number theory symposium, University of Wisconsin-Madison, WI, USA, July 16–20, 2018. Berkeley, CA: Mathematical Sciences Publishers (MSP). Open Book Ser. 2, 293-310 (2019).
Big prime field FFT on multi-core processors. (English) Zbl 1467.65121
Bradford, Russell (ed.), Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC ’19, Beijing, China, July 15–18, 2019. New York, NY: Association for Computing Machinery (ACM). 106-113 (2019).
Fast polynomial multiplication over \(\mathbb{F}_{2^{60}}\). (English) Zbl 1360.68935
Rosenkranz, Markus (ed.), Proceedings of the 41st international symposium on symbolic and algebraic computation, ISSAC 2016, Waterloo, Canada, July 20–22, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4380-0). 255-262 (2016).
A pseudo-polynomial time algorithm for solving the knapsack problem in polynomial space. (English) Zbl 1486.90165
Chan, T-H. Hubert (ed.) et al., Combinatorial optimization and applications. 10th international conference, COCOA 2016, Hong Kong, China, December 16–18, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10043, 624-638 (2016).
On the isomorphism of graphs having some eigenvalues of moderate multiplicity. (English) Zbl 1326.05081
Tighter Fourier transform lower bounds. (English) Zbl 1435.68108
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 14-25 (2015).
Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem. (English) Zbl 1319.68049
Analysis of speedups in parallel evolutionary algorithms and \((1 + \lambda)\) EAs for combinatorial optimization. (English) Zbl 1360.68783
The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm. (English) Zbl 1360.68788
Complexity of computation in finite fields. (English. Russian original) Zbl 1310.94241
J. Math. Sci., New York 191, No. 5, 661-685 (2013); translation from Fundam. Prikl. Mat. 17(2011/12), No. 4, 95-131 (2012).
Reviewer: Olaf Ninnemann (Berlin)
Adaptive drift analysis. (English) Zbl 1277.68289
Multiplicative drift analysis. (English) Zbl 1264.68220
Computational indistinguishability between quantum states and its cryptographic application. (English) Zbl 1275.81021
The use of tail inequalities on the probable computational time of randomized search heuristics. (English) Zbl 1242.68299
Running time analysis of ant colony optimization for shortest path problems. (English) Zbl 1250.68238
Reviewer: Thomas Jansen (Cork)
Runtime analysis of the \((1+1)\) evolutionary algorithm on strings over finite alphabets. (English) Zbl 1369.68303
Proceedings of the 11th ACM SIGEVO workshop on foundations of genetic algorithms, FOGA 2011, Schwarzenberg, Austria, January 5–9, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0633-1). 119-126 (2011).
Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers. (English) Zbl 1346.68250
Moreno Maza, Marc (ed.), Proceedings of the 2011 international workshop on symbolic-numeric computation, SNC 2011, San Jose, CA, USA, June 7–11, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0515-0). 54-62 (2011).
Fast Fourier transforms over poor fields. (English) Zbl 1323.68622
Leykin, Anton (ed.), Proceedings of the 36th international symposium on symbolic and algebraic computation, ISSAC 2011, San Jose, CA, USA, June 7–11, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0675-1). 289-296 (2011).
On the complexity of matroid isomorphism problem. (English) Zbl 1230.68115
Reviewer: Andreas Brandstädt (Rostock)
The complexity of symmetric Boolean parity Holant problems (extended abstract). (English) Zbl 1333.68144
Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 712-723 (2011).
Faster polynomial multiplication via discrete Fourier transforms. (English) Zbl 1330.68121
Kulikov, Alexander (ed.) et al., Computer science – theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20711-2/pbk). Lecture Notes in Computer Science 6651, 91-104 (2011).
On the OBDD complexity of the most significant bit of integer multiplication. (English) Zbl 1220.68059
Reviewer: Thomas Jansen (Cork)
New results on the most significant bit of integer multiplication. (English) Zbl 1209.68270
MSC:
68Q25
94C10
Randomized OBDDs for the most significant bit of multiplication need exponential size. (English) Zbl 1298.68109
Černá, Ivana (ed.) et al., SOFSEM 2011: Theory and practice of computer science. 37th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 22–28, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-18380-5/pbk). Lecture Notes in Computer Science 6543, 135-145 (2011).
Practical performance models of algorithms in evolutionary program induction and other domains. (English) Zbl 1210.68101
MSC:
68T20
The isomorphism problem for \(k\)-trees is complete for logspace. (English) Zbl 1250.68120
Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2009. 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24–28, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03815-0/pbk). Lecture Notes in Computer Science 5734, 537-548 (2009).
Representing groups on graphs. (English) Zbl 1250.05058
Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2009. 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24–28, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03815-0/pbk). Lecture Notes in Computer Science 5734, 295-306 (2009).
Computational complexity of computing a partial solution for the graph automorphism problems. (English) Zbl 1168.68020
On the complexity of the hidden subgroup problem. (English) Zbl 1139.68343
Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 70-81 (2008).
Complexity results in graph reconstruction. (English) Zbl 1117.05078
Reviewer: Josef Lauri (Msida)
LWPP and WPP are not uniformly gap-definable. (English) Zbl 1105.68045
MSC:
68Q15
Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs. (English) Zbl 1056.05099
MSC:
05C60
The size of SPP. (English) Zbl 1068.68064
MSC:
68Q15
An oracle builder’s toolkit. (English) Zbl 1025.68041
MSC:
68Q15
Filter Results by …
Document Type
- Journal Articles (50)
- Collection Articles (16)
all
top 5
Author
- Sudholt, Dirk (6)
- Harvey, David (5)
- van der Hoeven, Joris (5)
- Doerr, Benjamin (4)
- Bollig, Beate (3)
- Levet, Michael (3)
- Arvind, Vikraman (2)
- Covanov, Svyatoslav (2)
- Das, Bireswar (2)
- Fenner, Stephen A. (2)
- Gashkov, Sergey B. (2)
- Grochow, Joshua A. (2)
- Johannsen, Daniel (2)
- Köbler, Johannes (2)
- Kuhnert, Sebastian (2)
- Lässig, Jörg (2)
- Lecerf, Grégoire (2)
- Nagoya, Takayuki (2)
- Pospelov, Alexey (2)
- Sergeev, Igor’ Sergeevich (2)
- Thyssen, Christian (2)
- Toda, Seinosuke (2)
- Tripathi, Rahul (2)
- Ailon, Nir (1)
- Aleksashkina, A. A. (1)
- Allender, Eric W. (1)
- Brand, Michael (1)
- Collins, Nathaniel A. (1)
- Doerr, Carola (1)
- Dutta, Sagarmoy (1)
- Elsässer, Robert (1)
- Fortnow, Lance J. (1)
- Fujimoto, Noriyuki (1)
- Gheorghiu, Vlad (1)
- Gille, Marc (1)
- Goldberg, Leslie Ann (1)
- Graff, Mario (1)
- Guo, Heng (1)
- Han, Zhangang (1)
- Hemaspaandra, Edith (1)
- Hemaspaandra, Lane A. (1)
- Hitchcock, John M. (1)
- Jonsson, Peter (1)
- Kalachev, Gleb V. (1)
- Kawachi, Akinori (1)
- Klump, Jochen (1)
- Kobel, Alexander (1)
- Koshiba, Takeshi (1)
- Kostromin, A. N. (1)
- Kurtz, Stuart A. (1)
- Kurur, Piyush P. (1)
- Lebreton, Romain (1)
- Li, Lide (1)
- Lingas, Andrzej (1)
- Lu, Pinyan (1)
- Lu, Ruqian (1)
- Luo, Dan (1)
- Mareš, Martin (1)
- Matsuoka, Tatsuya (1)
- Mohajerani, Davood (1)
- Molin, Pascal (1)
- Moore, Cristopher (1)
- Moreno Maza, Marc (1)
- Morgan, Andrew (1)
- Nesterenko, Yuriĭ Valentinovich (1)
- Nishimura, Harumichi (1)
- Ohsaka, Naoto (1)
- Page, Aurel (1)
- Parvatov, Nikolaĭ Georgievich (1)
- Poli, Riccardo (1)
- Radziszowski, Stanisław P. (1)
- Raghavendra Rao, B. V. (1)
- Raß, Alexander (1)
- Rojas, J. Maurice (1)
- Rowe, Jonathan E. (1)
- Sadov, Sergey Yu. (1)
- Sagraloff, Michael (1)
- Sarma M. N., Jayalal (1)
- Schmidt, Martin (1)
- Schreiner, Jonas (1)
- Shleyfman, Alexander (1)
- Skresanov, Saveliĭ Vyacheslavovich (1)
- Spakowski, Holger (1)
- Storjohann, Arne (1)
- Sze, Tsz-Wo (1)
- Thomé, Emmanuel (1)
- Trinker, Horst (1)
- Uehara, Ryuhei (1)
- Valiant, Leslie Gabriel (1)
- van Melkebeek, Dieter (1)
- Vávra, Tomáš (1)
- Veneziano, Francesco (1)
- Wang, Linxiao (1)
- Wang, Yong (1)
- Wanka, Rolf (1)
- Winzen, Carola (1)
- Yamakami, Tomoyuki (1)
- Yang, Jing (1)
- Zhang, Jun (1)
- Zhang, Yong (1)
- and 3 more Authors
all
top 5
Serial
- Theor. Comput. Sci. (10)
- Algorithmica (5)
- Theory Comput. Syst. (3)
- Discrete Appl. Math. (2)
- J. Symb. Comput. (2)
- J. Complexity (2)
- Inf. Comput. (2)
- Linear Algebra Appl. (2)
- Artif. Intell. (1)
- Mosc. Univ. Math. Bull. (1)
- Phys. Lett., A (1)
- Math. Comput. (1)
- J. Comput. Syst. Sci. (1)
- J. Number Theory (1)
- SIAM J. Comput. (1)
- J. Cryptology (1)
- Int. J. Algebra Comput. (1)
- Australas. J. Comb. (1)
- Comput. Complexity (1)
- J. Math. Sci., New York (1)
- J. Artif. Intell. Res. (JAIR) (1)
- Soft Comput. (1)
- J. ACM (1)
- Ann. Math. (2) (1)
- J. Algebra Appl. (1)
- J. Discrete Algorithms (1)
- Chebyshevskiĭ Sb. (1)
- Diskretn. Anal. Issled. Oper. (1)
- Comput. Sci. Rev. (1)
- Res. Number Theory (1)
