Search results for "quasi-polynomial"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
45	Sven Verdoolaege, Rachid Seghir, Kristof Beyls, Vincent Loechner, Maurice Bruynooghe	Counting Integer Points in Parametric Polytopes Using Barvinok's Rational Functions.	Algorithmica	2007	DBLP DOI BibTeX RDF
37	Zeev Dvir, Amir Shpilka	Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.	STOC	2005	DBLP DOI BibTeX RDF	depth 3 circuits, locally decodable codes, polynomial identity testing
34	Zohar Shay Karnin, Amir Shpilka	Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In.	CCC	2008	DBLP DOI BibTeX RDF	PIT, depth-3, arithmetic circuit, deterministic, polynomial identity testing
31	Rafael Pass	Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition.	EUROCRYPT	2003	DBLP DOI BibTeX RDF
28	Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino	On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities.	ICALP	2001	DBLP DOI BibTeX RDF
25	Ashish V. Naik, Kenneth W. Regan, D. Sivakumar	Quasilinear Time Complexity Theory.	STACS	1994	DBLP DOI BibTeX RDF
23	Thomas Eiter, Kazuhisa Makino	On computing all abductive explanations from a propositional Horn theory.	J. ACM	2007	DBLP DOI BibTeX RDF	Horn theories, dualization problem, polynomial total-time computation, NP-hardness, Abduction, model-based reasoning, propositional logic, tractability, prime implicates, characteristic set, enumeration algorithms
23	Boaz Barak, Amit Sahai	How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation.	FOCS	2005	DBLP DOI BibTeX RDF
23	Jan Remy, Angelika Steger	A quasi-polynomial time approximation scheme for minimum weight triangulation.	J. ACM	2009	DBLP DOI BibTeX RDF	approximation algorithms, Minimum weight triangulation
23	Jan Remy, Angelika Steger	A quasi-polynomial time approximation scheme for minimum weight triangulation.	STOC	2006	DBLP DOI BibTeX RDF	approximation algorithms, minimum weight triangulation
23	Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan	An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals.	ESA	2003	DBLP DOI BibTeX RDF
23	Jochen Könemann, R. Ravi 0001	Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees.	FSTTCS	2003	DBLP DOI BibTeX RDF
23	Arkadev Chattopadhyay	Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits.	FOCS	2007	DBLP DOI BibTeX RDF
23	Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan	Matroid Intersections, Polymatroid Inequalities, and Related Problems.	MFCS	2002	DBLP DOI BibTeX RDF
22	John Fearnley, Sanjay Jain 0001, Bart de Keijzer, Sven Schewe, Frank Stephan 0001, Dominik Wojtczak	An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space.	Int. J. Softw. Tools Technol. Transf.	2019	DBLP DOI BibTeX RDF
22	John Fearnley, Sanjay Jain 0001, Sven Schewe, Frank Stephan 0001, Dominik Wojtczak	An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space.	CoRR	2017	DBLP BibTeX RDF
22	John Fearnley, Sanjay Jain 0001, Sven Schewe, Frank Stephan 0001, Dominik Wojtczak	An ordered approach to solving parity games in quasi polynomial time and quasi linear space.	SPIN	2017	DBLP DOI BibTeX RDF
21	Sven Verdoolaege, Rachid Seghir, Kristof Beyls, Vincent Loechner, Maurice Bruynooghe	Analytical computation of Ehrhart polynomials: enabling more compiler analyses and optimizations.	CASES	2004	DBLP DOI BibTeX RDF	Barvinok's decomposition, Ehrhart polynomial, parametric polytope, quasi-polynomial, signed unimodular decomposition, polyhedral model, compiler analysis
20	Roland Badeau, Bertrand David 0002, Gaël Richard	CramÉr-Rao Bounds for Multiple Poles and Coefficients of Quasi-Polynomials in Colored Noise.	IEEE Trans. Signal Process.	2008	DBLP DOI BibTeX RDF
20	Nikhil Bansal 0001, Amit Chakrabarti, Amir Epstein, Baruch Schieber	A quasi-PTAS for unsplittable flow on line graphs.	STOC	2006	DBLP DOI BibTeX RDF	scheduling, approximation algorithms, resource allocation, approximation scheme, unsplittable flow
20	André Berger, Artur Czumaj, Michelangelo Grigni, Hairong Zhao	Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs.	ESA	2005	DBLP DOI BibTeX RDF
20	Wolfgang Lindner 0002	Learning DNF by Statistical and Proper Distance Queries Under the Uniform Distribution.	ALT	2005	DBLP DOI BibTeX RDF
20	Daya Ram Gaur, Ramesh Krishnamurti	Average Case Self-Duality of Monotone Boolean Functions.	Canadian AI	2004	DBLP DOI BibTeX RDF	Machine Learning, Knowledge Representation, Satisfiability, Self-duality, Monotone Boolean Functions
17	Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma	If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	68Q17, 68Q15, 94A60, Subject classification. 68Q10
17	Amos Beimel, Enav Weinreb	Monotone Circuits for Weighted Threshold Functions.	CCC	2005	DBLP DOI BibTeX RDF
17	Khaled M. Elbassioni	Finding All Minimal Infrequent Multi-dimensional Intervals.	LATIN	2006	DBLP DOI BibTeX RDF
17	Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal	Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.	FOCS	2002	DBLP DOI BibTeX RDF
17	Khaled M. Elbassioni	An Algorithm for Dualization in Products of Lattices and Its Applications.	ESA	2002	DBLP DOI BibTeX RDF
14	Ruoxu Cen, Jason Li 0006, Debmalya Panigrahi	Hypergraph Unreliability in Quasi-Polynomial Time.	CoRR	2024	DBLP DOI BibTeX RDF
14	Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé	Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs.	SIAM J. Comput.	2024	DBLP DOI BibTeX RDF
14	Akanksha Agrawal 0001, Paloma T. Lima, Daniel Lokshtanov, Saket Saurabh 0001, Roohani Sharma	Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time.	SODA	2024	DBLP DOI BibTeX RDF
14	Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi	A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies.	CoRR	2023	DBLP DOI BibTeX RDF
14	Pawel Parys, Aleksander Wiacek	Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games.	CoRR	2023	DBLP DOI BibTeX RDF
14	Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski	Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time.	CoRR	2023	DBLP DOI BibTeX RDF
14	Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza	A tight quasi-polynomial bound for Global Label Min-Cut.	SODA	2023	DBLP DOI BibTeX RDF
14	Jeongmin Chae, Praneeth Narayanamurthy, Selin Bac, Shaama Mallikarjun Sharada, Urbashi Mitra	Column-Based Matrix Approximation with Quasi-Polynomial Structure.	ICASSP	2023	DBLP DOI BibTeX RDF
14	Rares-Darius Buhai, David Steurer	Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures.	COLT	2023	DBLP BibTeX RDF
14	Pawel Parys, Aleksander Wiacek	Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games.	CiE	2023	DBLP DOI BibTeX RDF
14	Mirmahdi Rahgoshay, Mohammad R. Salavatipour	Asymptotic Quasi-Polynomial Time Approximation Scheme for Resource Minimization for Fire Containment.	Algorithmica	2022	DBLP DOI BibTeX RDF
14	Khaled M. Elbassioni	Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
14	Zachary Friggstad, Chaitanya Swamy	A constant-factor approximation for directed latency in quasi-polynomial time.	J. Comput. Syst. Sci.	2022	DBLP DOI BibTeX RDF
14	Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza	A tight quasi-polynomial bound for Global Label Min-Cut.	CoRR	2022	DBLP DOI BibTeX RDF
14	Rohan Ghuge, Viswanath Nagarajan	Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems.	Math. Oper. Res.	2022	DBLP DOI BibTeX RDF
14	Cristian S. Calude, Sanjay Jain 0001, Bakhadyr Khoussainov, Wei Li 0050, Frank Stephan 0001	Deciding Parity Games in Quasi-polynomial Time.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
14	Reut Nomberg, Ilana Nisky	Human-in-the-Loop Stability Analysis of Haptic Rendering With Time Delay by Tracking the Roots of the Characteristic Quasi-Polynomial: The Effect of arm Impedance.	IEEE Robotics Autom. Lett.	2021	DBLP DOI BibTeX RDF
14	Rares-Darius Buhai, David Steurer	Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures.	CoRR	2021	DBLP BibTeX RDF
14	Geoffroy Couteau, Pierre Meyer	Breaking the Circuit-Size Barrier for Secure Computation under Quasi-Polynomial LPN.	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
14	Sándor Kisfaludi-Bak	A quasi-polynomial algorithm for well-spaced hyperbolic TSP.	J. Comput. Geom.	2021	DBLP DOI BibTeX RDF
14	Nolan J. Coble, Matthew Coudron	Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits.	FOCS	2021	DBLP DOI BibTeX RDF
14	Hyejung H. Jee, Carlo Sparaciari, Omar Fawzi, Mario Berta	Quasi-Polynomial Time Algorithms for Free Quantum Games in Bounded Dimension.	ICALP	2021	DBLP DOI BibTeX RDF
14	Geoffroy Couteau, Pierre Meyer	Breaking the Circuit Size Barrier for Secure Computation Under Quasi-Polynomial LPN.	EUROCRYPT (2)	2021	DBLP DOI BibTeX RDF
14	Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski	Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths.	SOSA	2021	DBLP DOI BibTeX RDF
14	André Arnold, Damian Niwinski, Pawel Parys	A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation.	CSL	2021	DBLP DOI BibTeX RDF
14	Sara Angulo, Raymundo Márquez, Miguel Bernal 0001	Quasi-Polynomial-Based Robust Stability of Time-Delay Systems Can be Less Conservative Than Lyapunov-Krasovskii Approaches.	IEEE Trans. Autom. Control.	2020	DBLP DOI BibTeX RDF
14	Michal Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese	Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs.	Algorithmica	2020	DBLP DOI BibTeX RDF
14	Peter Gartland, Daniel Lokshtanov	Independent Set on C≥-Free Graphs in Quasi-Polynomial Time.	CoRR	2020	DBLP BibTeX RDF
14	Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski	Quasi-polynomial-time algorithm for Independent Set in Pt-free and C>t-free graphs via shrinking the space of connecting subgraphs.	CoRR	2020	DBLP BibTeX RDF
14	Peter Gartland, Daniel Lokshtanov	Independent Set on Pk-Free Graphs in Quasi-Polynomial Time.	CoRR	2020	DBLP BibTeX RDF
14	Sándor Kisfaludi-Bak	A quasi-polynomial algorithm for well-spaced hyperbolic TSP.	CoRR	2020	DBLP BibTeX RDF
14	Nolan J. Coble, Matthew Coudron	Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits.	CoRR	2020	DBLP BibTeX RDF
14	Shuonan Wu, Ludmil T. Zikatanov	On the unisolvence for the quasi-polynomial spaces of differential forms.	CoRR	2020	DBLP BibTeX RDF
14	Reza Gheissari, Eyal Lubetzky	Quasi-polynomial mixing of critical two-dimensional random cluster models.	Random Struct. Algorithms	2020	DBLP DOI BibTeX RDF
14	Klaus Jansen, Lars Rohwedder	A Quasi-Polynomial Approximation for the Restricted Assignment Problem.	SIAM J. Comput.	2020	DBLP DOI BibTeX RDF
14	Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé	Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.	SODA	2020	DBLP DOI BibTeX RDF
14	Sándor Kisfaludi-Bak	Hyperbolic intersection graphs and (quasi)-polynomial time.	SODA	2020	DBLP DOI BibTeX RDF
14	Rohan Ghuge, Viswanath Nagarajan	Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems.	SODA	2020	DBLP DOI BibTeX RDF
14	Peter Gartland, Daniel Lokshtanov	Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time.	FOCS	2020	DBLP DOI BibTeX RDF
14	Zachary Friggstad, Chaitanya Swamy	A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time.	ESA	2020	DBLP DOI BibTeX RDF
14	Sándor Kisfaludi-Bak	A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP.	SoCG	2020	DBLP DOI BibTeX RDF
14	Mirmahdi Rahgoshay, Mohammad R. Salavatipour	Asymptotic Quasi-Polynomial Time Approximation Scheme for Resource Minimization for Fire Containment.	STACS	2020	DBLP DOI BibTeX RDF
14	Lijie Chen 0001	Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF
14	Giacomo Micheli	On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic.	SIAM J. Appl. Algebra Geom.	2019	DBLP DOI BibTeX RDF
14	Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé	Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.	CoRR	2019	DBLP BibTeX RDF
14	Thorsten Kleinjung, Benjamin Wesolowski	Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic.	CoRR	2019	DBLP BibTeX RDF
14	Pawel Parys	Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time.	CoRR	2019	DBLP BibTeX RDF
14	Khaled M. Elbassioni	Quasi-polynomial Algorithms for List-coloring of Nearly Intersecting Hypergraphs.	CoRR	2019	DBLP BibTeX RDF
14	Zachary Friggstad, Chaitanya Swamy	A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time.	CoRR	2019	DBLP BibTeX RDF
14	Thorsten Kleinjung, Benjamin Wesolowski	Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
14	Abhishek Jain 0002, Zhengzhong Jin	Statistical Zap Arguments from Quasi-Polynomial LWE.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
14	Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic 0001, Pawel Parys	Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games.	SODA	2019	DBLP DOI BibTeX RDF
14	Lijie Chen 0001	Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits.	FOCS	2019	DBLP DOI BibTeX RDF
14	Pawel Parys	Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time.	MFCS	2019	DBLP DOI BibTeX RDF
14	Michail Fasoulakis, Evangelos Markakis	An Improved Quasi-Polynomial Algorithm for Approximate Well-Supported Nash Equilibria.	AAAI	2019	DBLP DOI BibTeX RDF
14	Fabrizio Grandoni 0001, Bundit Laekhanukit, Shi Li 0001	O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm.	STOC	2019	DBLP DOI BibTeX RDF
14	Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala	Hilbert quasi-polynomial for order domains and application to coding theory.	Adv. Math. Commun.	2018	DBLP DOI BibTeX RDF
14	Michal Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese	Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs.	CoRR	2018	DBLP BibTeX RDF
14	Fabrizio Grandoni 0001, Bundit Laekhanukit, Shi Li 0001	O(log2k/log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.	CoRR	2018	DBLP BibTeX RDF
14	Laure Daviaud, Marcin Jurdzinski, Ranko Lazic 0001	A pseudo-quasi-polynomial algorithm for solving mean-payoff parity games.	CoRR	2018	DBLP BibTeX RDF
14	Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic 0001, Pawel Parys	Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games.	CoRR	2018	DBLP BibTeX RDF
14	Rohan Ghuge, Viswanath Nagarajan	A Quasi-Polynomial Algorithm for Submodular Tree Orienteering in Directed Graphs.	CoRR	2018	DBLP BibTeX RDF
14	Sándor Kisfaludi-Bak	Hyperbolic intersection graphs and (quasi)-polynomial time.	CoRR	2018	DBLP BibTeX RDF
14	Laure Daviaud, Marcin Jurdzinski, Ranko Lazic 0001	A pseudo-quasi-polynomial algorithm for mean-payoff parity games.	LICS	2018	DBLP DOI BibTeX RDF
14	Karoliina Lehtinen	A modal μ perspective on solving parity games in quasi-polynomial time.	LICS	2018	DBLP DOI BibTeX RDF
14	Michal Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese	Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs.	ESA	2018	DBLP DOI BibTeX RDF
14	Ramprasad Saptharishi, Anamay Tengse	Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees.	Electron. Colloquium Comput. Complex.	2017	DBLP BibTeX RDF
14	Klaus Jansen, Lars Rohwedder	A Quasi-Polynomial Approximation for the Restricted Assignment Problem.	CoRR	2017	DBLP BibTeX RDF
14	Hugo Gimbert, Rasmus Ibsen-Jensen	A short proof of correctness of the quasi-polynomial time algorithm for parity games.	CoRR	2017	DBLP BibTeX RDF
14	Ramprasad Saptharishi, Anamay Tengse	Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees.	CoRR	2017	DBLP BibTeX RDF
14	Klaus Jansen, Lars Rohwedder	A Quasi-Polynomial Approximation for the Restricted Assignment Problem.	IPCO	2017	DBLP DOI BibTeX RDF
14	Amariah Becker, Philip N. Klein, David Saulpic	A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs.	ESA	2017	DBLP DOI BibTeX RDF