×

Found 181 Documents (Results 1–100)

Matrix rigidity depends on the target field. (English) Zbl 07711623

Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 41, 26 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Canonical form for graphs in quasipolynomial time: preliminary report. (English) Zbl 1433.68165

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 1237-1246 (2019).
PDFBibTeX XMLCite
Full Text: DOI

List-decoding homomorphism codes with arbitrary codomains. (English) Zbl 1527.94083

Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 29, 18 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Group, graphs, algorithms: the graph isomorphism problem. (English) Zbl 1490.68116

Sirakov, Boyan (ed.) et al., Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1–9, 2018. Volume IV. Invited lectures. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM). 3319-3336 (2018).
PDFBibTeX XMLCite
Full Text: DOI Link

Graph isomorphism in quasipolynomial time (extended abstract). (English) Zbl 1376.68058

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 684-697 (2016).
PDFBibTeX XMLCite
Full Text: DOI

On the automorphism groups of strongly regular graphs. I. (English) Zbl 1365.05202

Proceedings of the 5th conference on innovations in theoretical computer science, ITCS’14, Princeton, NJ, USA, January 11–14, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2243-0). 359-368 (2014).
PDFBibTeX XMLCite
Full Text: DOI

Quasipolynomial-time canonical form for Steiner designs. (English) Zbl 1293.05028

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 261-270 (2013).
MSC:  05B25 05C60 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Polynomial-time isomorphism test for groups with no abelian normal subgroups (extended abstract). (English) Zbl 1272.68475

Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9–13, 2012. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-31593-0/pbk). Lecture Notes in Computer Science 7391, 51-62 (2012).
PDFBibTeX XMLCite
Full Text: DOI

Polynomial-time isomorphism test for groups with abelian Sylow towers. (English) Zbl 1248.20001

Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th – March 3rd, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPIcs – Leibniz International Proceedings in Informatics 14, 453-464, electronic only (2012).
PDFBibTeX XMLCite
Full Text: DOI

Code equivalence and group isomorphism. (English) Zbl 1382.20037

Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1395-1408 (2011).
PDFBibTeX XMLCite
Full Text: Link

Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas. (English) Zbl 1332.68003

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, 162-180 (2011).
MSC:  68-03 20-03 20B40 20P05 68Q17 68Q25 68Q87
PDFBibTeX XMLCite
Full Text: DOI

Evasiveness and the distribution of prime numbers. (English) Zbl 1230.68098

Marion, Jean-Yves (ed.) et al., STACS 2010. 27th international symposium on theoretical aspects of computer science, Nancy, France, March 4–6, 2010. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-16-3). LIPIcs – Leibniz International Proceedings in Informatics 5, 71-82, electronic only (2010).
PDFBibTeX XMLCite
Full Text: DOI Link

Weights of exact threshold functions. (English) Zbl 1287.94129

Hliněný, Petr (ed.) et al., Mathematical foundations of computer science 2010. 35th international symposium, MFCS 2010, Brno, Czech Republic, August 23–27, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15154-5/pbk). Lecture Notes in Computer Science 6281, 66-77 (2010).
MSC:  94C11 94D10 68Q15
PDFBibTeX XMLCite
Full Text: DOI

Polynomial-time theory of matrix groups. (English) Zbl 1304.68065

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 55-64 (2009).
MSC:  68Q25 20H30 68W20
PDFBibTeX XMLCite
Full Text: DOI

Product growth and mixing in finite groups. (English) Zbl 1192.60016

Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 248-257 (2008).
MSC:  60B15 20P05
PDFBibTeX XMLCite

Sandpile transience on the grid is polynomially bounded. (English) Zbl 1302.82065

Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 627-636 (2007).
MSC:  82C20 05C25 05C90
PDFBibTeX XMLCite

On the diameter of Eulerian orientations of graphs. (English) Zbl 1192.05084

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 822-831 (2006).
MSC:  05C45 05C12
PDFBibTeX XMLCite
Full Text: DOI

Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. (English) Zbl 1297.68080

Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 1057-1066 (2005).
MSC:  68Q17 05A05 20B30
PDFBibTeX XMLCite

Simultaneous Diophantine approximation with excluded primes. (English) Zbl 1318.11086

Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-558-X). 1123-1129 (2004).
MSC:  11J13 11Y16 68Q25
PDFBibTeX XMLCite

On the diameter of the symmetric group: polynomial bounds. (English) Zbl 1318.20002

Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-558-X). 1108-1112 (2004).
MSC:  20B30 20F05
PDFBibTeX XMLCite

Recognizing simplicity of black-box groups and the frequency of \(p\)-singular elements in affine groups. (English) Zbl 1052.20031

Kantor, William M. (ed.) et al., Groups and computation III. Proceedings of the international conference at the Ohio State University, Columbus, OH, USA, June 15–19, 1999. Berlin: Walter de Gruyter (ISBN 3-11-016721-2/hbk). Ohio State Univ. Math. Res. Inst. Publ. 8, 39-62 (2001).
MSC:  20G40 20D06 68W30
PDFBibTeX XMLCite

Strong bias of group generators: an obstacle to the “product replacement algorithm”. (English) Zbl 1005.20055

Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 9-11, 2000. Philadelphia, PA: SIAM. 627-635 (2000).
MSC:  20P05 68W30 20F05 60G50 20B40
PDFBibTeX XMLCite

Paul Erdős (1913–1996): His influence on the theory of computing. (English) Zbl 0963.68071

STOC ’97. Proceedings of the 29th annual ACM symposium on theory of computing, El Paso, TX, USA, May 4-6, 1997. New York, NY: ACM, Association for Computing Machinery, 383-401 (1999).
MSC:  68Q05 68-03
PDFBibTeX XMLCite

A polynomial-time theory of black box groups. I. (English) Zbl 0942.20032

Campbell, C. M. (ed.) et al., Groups St. Andrews 1997 in Bath. Selected papers of the international conference, Bath, UK, July 26-August 9, 1997. Vol. 1. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 260, 30-64 (1999).
PDFBibTeX XMLCite

The cost of the missing bit: Communication complexity with help. (English) Zbl 1052.68623

STOC ’98. Proceedings of the 30th annual ACM symposium on theory of computing, Dallas, TX, USA, May 23–26, 1998. New York, NY: ACM, Association for Computing Machinery (ISBN 0-89791-962-9). 673-682 (1998).
MSC:  68Q25
PDFBibTeX XMLCite

The growth rate of vertex-transitive planar graphs. (English) Zbl 1321.05059

Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, SODA ’97, New Orleans, LA, January 5–7, 1997. Philadelphia, PA: SIAM; New York, NY: ACM (ISBN 0-89871-390-0). 564-573 (1997).
MSC:  05C10 05C85
PDFBibTeX XMLCite

Randomized simultaneous messages: Solution of a problem of Gao in communication complexity. (English) Zbl 0995.68052

12th annual IEEE conference on computational complexity, CCC ’97. Proceedings of the conference, Ulm, Germany, June 24-27, 1997. Los Alamitos, CA: IEEE Computer Society. 239-246 (1997).
MSC:  68Q15 68Q10 68Q25
PDFBibTeX XMLCite

Communication complexity. (English) Zbl 0941.68088

Privara, L. (ed.) et al., Mathematical foundations of computer science 1997. 22nd international symposium, MFCS ’97, Bratislava, Slovakia, August 25-29, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1295, 5-18 (1997).
MSC:  68Q85
PDFBibTeX XMLCite

Multiplicative equations over commuting matrices. (English) Zbl 0865.15012

Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, held in Atlanta, GA, USA, January 28-30, 1996. Philadelphia, PA: SIAM. 498-507 (1996).
MSC:  15A24 65F30
PDFBibTeX XMLCite

Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs. (English) Zbl 0915.05076

Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22–24, 1996. New York, NY: ACM, 603-611 (1996).
PDFBibTeX XMLCite

Simultaneous messages vs. communication. (English) Zbl 1379.68125

Mayr, Ernst W. (ed.) et al., STACS 95. 12th annual symposium on theoretical aspects of computer science, Munich, Germany, March 2–4, 1995. Proceedings. Berlin: Springer-Verlag (ISBN 3-540-59042-0). Lecture Notes in Computer Science 900, 361-372 (1995).
MSC:  68Q10 68Q15 91A80
PDFBibTeX XMLCite
Full Text: DOI

Transparent (holographic) proofs. (English) Zbl 0790.68043

Enjalbert, Patrice (ed.) et al., STACS 93. 10th annual symposium on theoretical aspects of computer science, Würzburg, Germany, February 25-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 665, 525-534 (1993).
MSC:  68Q15
PDFBibTeX XMLCite

Computing composition series in primitive groups. (English) Zbl 0816.20006

Finkelstein, Larry (ed.) et al., Groups and computation. Papers from the workshop held at DIMACS, Rutgers University, New Brunswick, NJ (USA), October 7-10, 1991. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 11, 1-16 (1993).
MSC:  20B40 68W30 20B15 68Q25 20D30
PDFBibTeX XMLCite

Deciding finiteness of matrix groups in deterministic polynomial time. (English) Zbl 0925.20001

Bronstein, Manuel (ed.), ISSAC ’93. Proceedings of the 1993 international symposium on Symbolic and algebraic computation, Kiev, Ukraine, July 6–8, 1993. Baltimore, MD: ACM Press. 117-126 (1993).
PDFBibTeX XMLCite

Decomposition of *-closed algebras in polynomial time. (English) Zbl 0927.68121

Bronstein, Manuel (ed.), ISSAC ’93. Proceedings of the 1993 international symposium on Symbolic and algebraic computation, Kiev, Ukraine, July 6–8, 1993. Baltimore, MD: ACM Press. 86-94 (1993).
MSC:  68W30 68Q25
PDFBibTeX XMLCite

Deciding finiteness of matrix groups in Las Vegas polynomial time. (English) Zbl 0828.20032

Frederickson, Greg (ed.), Proceedings of the third annual ACM-SIAM symposium on discrete algorithms, held January 27-29, 1992, in Orlando, FL, USA. Philadelphia, PA: SIAM. 33-40 (1992).
PDFBibTeX XMLCite

Nearly linear time algorithms for permutation groups with a small base. (English) Zbl 0925.20011

Watt, Stephen M. (ed.), ISSAC ’91. Proceedings of the 1991 international symposium on Symbolic and algebraic computation. Bonn, Germany, July 15–17, 1991. New York, NY: ACM Press, 200-209 (1991).
MSC:  20B40 68W30
PDFBibTeX XMLCite

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference

Software