×

Found 152 Documents (Results 1–100)

Exact algorithms and hardness results for geometric red-blue hitting set problem. (English) Zbl 1528.68387

Li, Minming (ed.) et al., Frontiers of algorithmic wisdom. International joint conference, IJTCS-FAW 2022, Hong Kong, China, August 15–19, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13461, 176-191 (2023).
MSC:  68U05 68Q17 68W40
PDFBibTeX XMLCite
Full Text: DOI

Dynamic kernels for hitting sets and set packing. (English) Zbl 07803585

Golovach, Petr A. (ed.) et al., 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 214, Article 7, 18 p. (2021).
MSC:  68Q25 68Q27 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Anonymity-preserving space partitions. (English) Zbl 07788605

Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 32, 16 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Improved hitting set for orbit of ROABPs. (English) Zbl 07768375

Wootters, Mary (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 24th international conference, APPROX 2021, and 25th international conference, RANDOM 2021, University of Washington, Seattle, Washington, US (virtual conference), August 16–18, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 207, Article 30, 23 p. (2021).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. (English) Zbl 07711593

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 11, 27 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized complexity of \(d\)-hitting set with quotas. (English) Zbl 1490.68122

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 293-307 (2021).
MSC:  68Q27 68R10 90C27
PDFBibTeX XMLCite
Full Text: DOI

Discriminating codes in geometric setups. (English) Zbl 07765382

Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 24, 16 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Dynamic geometric set cover and hitting set. (English) Zbl 07760131

Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 2, 15 p. (2020).
MSC:  68U05 68-06 68P05
PDFBibTeX XMLCite
Full Text: DOI

Kernelizing the hitting set problem in linear sequential and constant parallel time. (English) Zbl 07759277

Albers, Susanne (ed.), 17th Scandinavian symposium and workshops on algorithm theory, SWAT 2020, Tórshavn, Faroe Islands, June 22–24, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 162, Article 9, 16 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

On nonadaptive security reductions of hitting set generators. (English) Zbl 07758317

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 15, 14 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Polynomial identity testing for low degree polynomials with optimal randomness. (English) Zbl 07758310

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 8, 13 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

On hitting-set generators for polynomials that vanish rarely. (English) Zbl 07758309

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 7, 23 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Improved explicit hitting-sets for ROABPs. (English) Zbl 07758306

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 4, 16 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. (English) Zbl 07561748

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 20, 47 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Abstract cores in implicit hitting set MaxSat solving. (English) Zbl 07331027

Pulina, Luca (ed.) et al., Theory and applications of satisfiability testing – SAT 2020. 23rd international conference, Alghero, Italy, July 3–10, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12178, 277-294 (2020).
MSC:  68Q25 68R07 68T20
PDFBibTeX XMLCite
Full Text: DOI

Parameterized dynamic variants of red-blue dominating set. (English) Zbl 1440.68134

Chatzigeorgiou, Alexander (ed.) et al., SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12011, 236-247 (2020).
MSC:  68Q27 05C69
PDFBibTeX XMLCite
Full Text: DOI Link

Faster FPT algorithm for 5-path vertex cover. (English) Zbl 07561676

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 32, 13 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs. (English) Zbl 1520.68107

Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 10, 14 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

New results on a family of geometric hitting set problems in the plane. (English) Zbl 1435.68350

Li, Yingshu (ed.) et al., Combinatorial optimization and applications. 13th international conference, COCOA 2019, Xiamen, China, December 13–15, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11949, 387-399 (2019).
MSC:  68U05 68Q17 68W25
PDFBibTeX XMLCite
Full Text: DOI

Fair hitting sequence problem: scheduling activities with varied frequency requirements. (English) Zbl 1525.90195

Heggernes, Pinar (ed.), Algorithms and complexity. 11th international conference, CIAC 2019, Rome, Italy, May 27–29, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11485, 174-186 (2019).
PDFBibTeX XMLCite
Full Text: DOI

Minimum membership covering and hitting. (English) Zbl 1522.68664

Das, Gautam K. (ed.) et al., WALCOM: algorithms and computation. 13th international conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11355, 394-406 (2019).
MSC:  68U05 68Q17 68W25
PDFBibTeX XMLCite
Full Text: DOI

Parameterized query complexity of hitting set using stability of sunflowers. (English) Zbl 07561379

Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 25, 12 p. (2018).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Towards blackbox identity testing of log-variate circuits. (English) Zbl 1499.68390

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 54, 16 p. (2018).
MSC:  68W20 68Q06
PDFBibTeX XMLCite
Full Text: DOI

Algebraic dependencies and PSPACE algorithms in approximative complexity. (English) Zbl 1442.68062

Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 10, 21 p. (2018).
MSC:  68Q15 14Q20 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set. (English) Zbl 1485.68264

Bender, Michael A. (ed.) et al., Latin 2018: theoretical informatics. 13th Latin American symposium, Buenos Aires, Argentina, April 16–19, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10807, 187-200 (2018).
MSC:  68U05 68Q27
PDFBibTeX XMLCite
Full Text: DOI Link

A PSPACE construction of a hitting set for the closure of small algebraic circuits. (English) Zbl 1428.68171

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1180-1192 (2018).
MSC:  68Q25 68Q06
PDFBibTeX XMLCite
Full Text: DOI arXiv

Bootstrapping variables in algebraic circuits. (English) Zbl 1427.68356

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1166-1179 (2018).
PDFBibTeX XMLCite
Full Text: DOI

Computational complexity for the problem of optimal intersection of straight line segments by disks. (English. Russian original) Zbl 1414.05093

Proc. Steklov Inst. Math. 303, Suppl. 1, S146-S155 (2018); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 23, No. 3, 171-181 (2017).
MSC:  05C10 05C62 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Hitting and covering partially. (English) Zbl 1509.68106

Wang, Lusheng (ed.) et al., Computing and combinatorics. 24th international conference, COCOON 2018, Qing Dao, China, July 2–4, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10976, 751-763 (2018).
PDFBibTeX XMLCite
Full Text: DOI

Exact algorithms via multivariate subroutines. (English) Zbl 1441.68181

Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 69, 13 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Improved bounds for quantified derandomization of constant-depth circuits and polynomials. (English) Zbl 1440.68131

O’Donnell, Ryan (ed.), 32nd computational complexity conference, CCC 2017, July 6–9, 2017, Riga, Latvia. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 79, Article 13, 48 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Efficient algorithms for \(k\)-regret minimizing sets. (English) Zbl 1432.68112

Iliopoulos, Costas S. (ed.) et al., 16th international symposium on experimental algorithms, SEA 2017, London, UK, June 21–23, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 75, Article 7, 23 p. (2017).
MSC:  68P15 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

An efficient algorithm for placing electric vehicle charging stations. (English) Zbl 1398.68657

Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 7, 12 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Lower bounds on same-set inner product in correlated spaces. (English) Zbl 1398.60020

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 19th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2016, and the 20th international workshop on randomization and computation, RANDOM 2016, Paris, France, September 7–9, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-018-7). LIPIcs – Leibniz International Proceedings in Informatics 60, Article 34, 11 p. (2016).
MSC:  60C05 05D40 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Hitting set for hypergraphs of low VC-dimension. (English) Zbl 1397.68092

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 23, 18 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized hardness of art gallery problems. (English) Zbl 1397.68091

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 19, 17 p. (2016).
MSC:  68Q25 68Q17 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Separating a Voronoi diagram via local search. (English) Zbl 1387.68240

Fekete, Sándor (ed.) et al., 32nd international symposium on computational geometry, SoCG’16, Boston, MA, USA, June 14–17, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-009-5). LIPIcs – Leibniz International Proceedings in Informatics 51, Article 18, 16 p. (2016).
MSC:  68U05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Identity testing for constant-width, and commutative, read-once oblivious ABPs. (English) Zbl 1380.68224

Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 29, 16 p. (2016).
MSC:  68Q25 12Y05 68P05
PDFBibTeX XMLCite
Full Text: DOI

Pseudorandomness when the odds are against you. (English) Zbl 1380.68434

Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 9, 35 p. (2016).
MSC:  68W20 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. (English) Zbl 1388.68118

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 323-346 (2015).
MSC:  68Q25 68Q05
PDFBibTeX XMLCite
Full Text: DOI

Quick but odd growth of cacti. (English) Zbl 1372.68135

Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 258-269 (2015).
PDFBibTeX XMLCite
Full Text: DOI

The container selection problem. (English) Zbl 1375.68034

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 416-434 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Near-linear algorithms for geometric hitting sets and set covers. (English) Zbl 1398.68656

Proceedings of the 30th annual symposium on computational geometry, SoCG ’14, Kyoto, Japan, June 8–11, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2594-3). 271-279 (2014).
PDFBibTeX XMLCite
Full Text: DOI

Progress on polynomial identity testing. II. (English) Zbl 1345.68182

Agrawal, Manindra (ed.) et al., Perspectives in computational complexity. The Somenath Biswas anniversary volume. Selected papers based on the presentations at the workshop, Kanpur, India, Summer 2012. Cham: Birkhäuser/Springer (ISBN 978-3-319-05445-2/hbk; 978-3-319-05446-9/ebook). Progress in Computer Science and Applied Logic 26, 131-146 (2014).
MSC:  68Q25 12Y05 13P05 68Q05 68Q17 68W30 68-02
PDFBibTeX XMLCite
Full Text: DOI

Set cover, set packing and hitting set for tree convex and tree-like set systems. (English) Zbl 1405.68144

Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 11th annual conference, TAMC 2014, Chennai, India, April 11–13, 2014. Proceedings. Berlin: Springer (ISBN 978-3-319-06088-0/pbk). Lecture Notes in Computer Science 8402, 248-258 (2014).
PDFBibTeX XMLCite
Full Text: DOI

Hitting Buneman circles. (English) Zbl 1397.68224

Tannen, Val (ed.) et al., In search of elegance in the theory and practice of computation. Essays dedicated to Peter Buneman. Berlin: Springer (ISBN 978-3-642-41659-0/pbk; 978-3-642-41660-6/ebook). Lecture Notes in Computer Science 8000, 250-258 (2013).
MSC:  68W25 68M11 90B80
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software