Search results for "polynomially-bounded"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
53	Klaus Wich	Characterization of Context-Free Languages with Polynomially Bounded Ambiguity.	MFCS	2001	DBLP DOI BibTeX RDF
51	Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf	The Polynomially Bounded Perfect Matching Problem Is in NC 2.	STACS	2007	DBLP DOI BibTeX RDF
50	Pavel Naumov	Upper bounds on complexity of Frege proofs with limited use of certain schemata.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF
42	Atsuko Yamaguchi, Hiroshi Mamitsuka	Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees.	ISAAC	2003	DBLP DOI BibTeX RDF
39	Juha Honkala	The Equivalence Problem of Polynomially Bounded D0L Systems - a Bound Depending Only on the Size of the Alphabet.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
36	Toniann Pitassi, Alasdair Urquhart	The Complexity of the Hajós Calculus	FOCS	1992	DBLP DOI BibTeX RDF	Hajos calculus, nondeterministic procedure, polynomially-bounded, Frege proof systems, complexity, graph theory
36	Wolfgang Maass 0001, Georg Schnitger, Eduardo D. Sontag	On the Computational Power of Sigmoid versus Boolean Threshold Circuits	FOCS	1991	DBLP DOI BibTeX RDF	polynomially bounded weights, sigmoid threshold gates, smooth threshold gates, depth 2 circuits, Boolean threshold circuits, constant size circuits, Boolean threshold gates, polynomial size sigmoid threshold circuits, Boolean functions, computational power, constant depth circuits
36	Dima Grigoriev, Marek Karpinski, Michael F. Singer	Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents	FOCS	1990	DBLP DOI BibTeX RDF	polynomial parallel time, sparse rational functions, polynomially bounded storage, interpolation, queries, sparse representation, black box
36	Ramamohan Paturi, Michael E. Saks	On Threshold Circuits for Parity	FOCS	1990	DBLP DOI BibTeX RDF	size-depth tradeoffs, almost optimal lower bound, polynomially bounded weights, neural networks, Boolean functions, rational approximation, parity, threshold circuits
30	Elias Dahlhaus, Marek Karpinski	A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract).	SWAT	1988	DBLP DOI BibTeX RDF
28	Yair Amir, Paul Bunn, Rafail Ostrovsky	Authenticated Adversarial Routing.	TCC	2009	DBLP DOI BibTeX RDF	End-to-End Communication, Communication Complexity, Error-Correction, Network Routing, Fault Localization, Multi-Party Computation
28	Jan Chomicki	Polynomial Time Query Processing in Temporal Deductive Databases.	PODS	1990	DBLP DOI BibTeX RDF
26	Hassan Sfouli	Nondefinability results with entire functions of finite order in polynomially bounded o-minimal structures.	Arch. Math. Log.	2024	DBLP DOI BibTeX RDF
26	Hassan Sfouli	Extension of C∞ functions in polynomially bounded o-minimal structure.	Ann. Pure Appl. Log.	2022	DBLP DOI BibTeX RDF
26	Hasan Eruslu, Francisco-Javier Sayas	Polynomially bounded error estimates for Trapezoidal Rule Convolution Quadrature.	Comput. Math. Appl.	2020	DBLP DOI BibTeX RDF
26	Hassan Sfouli	Some nondefinability results with entire functions in a polynomially bounded o-minimal structure.	Arch. Math. Log.	2020	DBLP DOI BibTeX RDF
26	Mohammad Ardeshir, Erfan Khaniki, Mohsen Shahriari	A Counterexample to Polynomially Bounded Realizability of Basic Arithmetic.	Notre Dame J. Formal Log.	2019	DBLP DOI BibTeX RDF
26	Flavio Ferrarotti, Loredana Tec, José Maria Turull Torres	Polynomially Bounded Valuations in Higher-Order Logics over Relational Databases.	Models: Concepts, Theory, Logic, Reasoning and Semantics	2018	DBLP BibTeX RDF
26	Vernon Asuncion, Yan Zhang 0003, Heng Zhang 0006	Polynomially Bounded Logic Programs with Function Symbols: A New Decidable.	AAAI	2017	DBLP DOI BibTeX RDF
26	Hiroyuki Okazaki, Yuichi Futa	Formalization of Polynomially Bounded and Negligible Functions Using the Computer-Aided Proof-Checking System Mizar.	FM4M/MathUI/ThEdu/DP/WIP@CIKM	2016	DBLP BibTeX RDF
26	Hiroyuki Okazaki	Algebra of Polynomially Bounded Sequences and Negligible Functions.	Formaliz. Math.	2015	DBLP DOI BibTeX RDF
26	Hiroyuki Okazaki, Yuichi Futa	Polynomially Bounded Sequences and Polynomial Sequences.	Formaliz. Math.	2015	DBLP DOI BibTeX RDF
26	Yi Zhou	Polynomially Bounded Forgetting.	PRICAI	2014	DBLP DOI BibTeX RDF
26	David A. Cohen, Martin C. Cooper, Martin James Green, Dániel Marx	On Guaranteeing Polynomially Bounded Search Tree Size.	CP	2011	DBLP DOI BibTeX RDF
26	Andreas Fischer 0008	Infinitely Peano differentiable functions in polynomially bounded o-minimal structures.	Ann. Pure Appl. Log.	2010	DBLP DOI BibTeX RDF
26	Johannes Waldmann	Polynomially Bounded Matrix Interpretations.	RTA	2010	DBLP DOI BibTeX RDF
26	Marcus Tressl	Heirs of box types in polynomially bounded structures.	J. Symb. Log.	2009	DBLP DOI BibTeX RDF
26	László Babai, Igor Gorodezky	Sandpile transience on the grid is polynomially bounded.	SODA	2007	DBLP BibTeX RDF
26	Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf	The polynomially bounded perfect matching problem is in NC^2.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
26	Dennis Hofheinz, Dominique Unruh	Simulatable Security and Polynomially Bounded Concurrent Composition.	IACR Cryptol. ePrint Arch.	2006	DBLP BibTeX RDF
26	Dennis Hofheinz, Dominique Unruh	Simulatable Security and Polynomially Bounded Concurrent Composability.	S&P	2006	DBLP DOI BibTeX RDF	Reactive Simulatability, Universal Composability, concurrent composition
26	Saeed Salehi	Polynomially Bounded Recursive Realizability.	Notre Dame J. Formal Log.	2005	DBLP DOI BibTeX RDF
26	Rafal Pierzchala	UPC condition in polynomially bounded o-minimal structures.	J. Approx. Theory	2005	DBLP DOI BibTeX RDF
26	Marcus Tressl	The elementary theory of Dedekind cuts in polynomially bounded structures.	Ann. Pure Appl. Log.	2005	DBLP DOI BibTeX RDF
26	Atsuko Yamaguchi, Kiyoko F. Aoki, Hiroshi Mamitsuka	Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees.	Inf. Process. Lett.	2004	DBLP DOI BibTeX RDF
26	Nader H. Bshouty, Dmitry Gavinsky	On Boosting with Polynomially Bounded Distributions.	J. Mach. Learn. Res.	2002	DBLP BibTeX RDF
26	Leonid Gurvits, Leiba Rodman	Convergence of Polynomially Bounded Semigroups of Matrices.	SIAM J. Matrix Anal. Appl.	1997	DBLP DOI BibTeX RDF
26	Domenico Zambella	Notes on Polynomially Bounded Arithmetic.	J. Symb. Log.	1996	DBLP DOI BibTeX RDF
26	Anne Condon, Richard E. Ladner	Interactive Proof Systems with Polynomially Bounded Strategies.	J. Comput. Syst. Sci.	1995	DBLP DOI BibTeX RDF
26	Viggo Kann	Polynomially Bounded Minimization Problems That Are Hard to Approximate.	Nord. J. Comput.	1994	DBLP BibTeX RDF
26	Viggo Kann	Polynomially Bounded Minimization Problems which are Hard to Approximate.	ICALP	1993	DBLP DOI BibTeX RDF
26	Sanjay Gupta	On the Closure of Certain Function Classes Under Integer Division by Polynomially-Bounded Functions.	Inf. Process. Lett.	1992	DBLP DOI BibTeX RDF
26	Anne Condon, Richard E. Ladner	Interactive Proof Systems with Polynomially Bounded Strategies.	SCT	1992	DBLP DOI BibTeX RDF
26	Milind Tambe, Paul S. Rosenbloom	A Frameworkfor Investigating Production System Formulations with Polynomially Bounded Match.	AAAI	1990	DBLP BibTeX RDF
26	Benjamin D. Smith, Paul S. Rosenbloom	Incremental Non-Backtracking Focusing: A Polynomially Bounded Generalization Algorithm for Version Spaces.	AAAI	1990	DBLP BibTeX RDF
26	Dima Grigoriev, Marek Karpinski	The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract)	FOCS	1987	DBLP DOI BibTeX RDF
26	Fred W. Glover, Darwin Klingman, Nancy V. Phillips	A New Polynomially Bounded Shortest Path Algorithm.	Oper. Res.	1985	DBLP DOI BibTeX RDF
26	R. Chandrasekaran, Arie Tamir	Polynomially bounded algorithms for locating p-centers on a tree.	Math. Program.	1982	DBLP DOI BibTeX RDF
26	Richard V. Helgason, Jeffery L. Kennington, H. S. Lall	A polynomially bounded algorithm for a singly constrained quadratic program.	Math. Program.	1980	DBLP DOI BibTeX RDF
26	Juhani Karhumäki	The Decidability of the Equivalence Problem for Polynomially Bounded DOL Sequences.	RAIRO Theor. Informatics Appl.	1977	DBLP DOI BibTeX RDF
25	Tim Nieberg, Johann L. Hurink, Walter Kern	Approximation schemes for wireless networks.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	bounded growth, Wireless ad-hoc networks, PTAS, maximum independent set, minimum dominating set
25	Daniel Bienstock, Mark Zuckerberg	Approximate fixed-rank closures of covering problems.	Math. Program.	2006	DBLP DOI BibTeX RDF
25	Dirk Sudholt	Crossover is provably essential for the ising model on trees.	GECCO	2005	DBLP DOI BibTeX RDF	expected optimization time, mutation vs. crossover, ising model, theoretical analysis, fitness sharing
25	Nikhil Bansal 0001	On minimizing the total flow time on multiple machines.	SODA	2004	DBLP BibTeX RDF
25	László Babai, Robert Beals, Ákos Seress	On the diameter of the symmetric group: polynomial bounds.	SODA	2004	DBLP BibTeX RDF
23	Rahul Santhanam	On Separators, Segregators and Time versus Space.	CCC	2001	DBLP DOI BibTeX RDF
21	Nikhil Bansal 0001, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour	A logarithmic approximation for unsplittable flow on line graphs.	SODA	2009	DBLP DOI BibTeX RDF
21	Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri, Zuheir Montazeri	Computational Power of the Quantum Turing Automata.	ITNG	2007	DBLP DOI BibTeX RDF
20	Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik	Complexity of Semi-algebraic Proofs.	STACS	2002	DBLP DOI BibTeX RDF
20	Martin Otto 0001	The Logic of Explicitly Presentation-Invariant Circuits.	CSL	1996	DBLP DOI BibTeX RDF	generic computation, Circuit complexity, finite model theory
20	Lin Chen 0001	Efficient Deterministic Parallel Algorithms for Integer Sorting.	ICCI	1990	DBLP DOI BibTeX RDF	Resource Tradeoff, Parallel Computation, Lower Bound, Sorting, PRAM, Algorithm Design and Analysis, Prefix Sum, Lexicographic Order, NC
16	Holger Dell, Dieter van Melkebeek	Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.	STOC	2010	DBLP DOI BibTeX RDF	arithmetic progression free sets, hereditary graph properties, vertex deletion problems, satisfiability, kernelization, vertex cover, parameterized complexity, probabilistically checkable proofs, feedback vertex set, sparsification
16	László Babai	On the diameter of Eulerian orientations of graphs.	SODA	2006	DBLP DOI BibTeX RDF
16	Ugo Dal Lago, Martin Hofmann 0001	Quantitative Models and Implicit Complexity.	FSTTCS	2005	DBLP DOI BibTeX RDF
16	Eike Kiltz, Hans Ulrich Simon	Complexity Theoretic Aspects of Some Cryptographic Functions.	COCOON	2003	DBLP DOI BibTeX RDF
16	Albert Atserias, Nicola Galesi, Ricard Gavaldà	Monotone Proofs of the Pigeon Hole Principle.	ICALP	2000	DBLP DOI BibTeX RDF
16	Hubert Comon, Florent Jacquemard	Ground Reducibility is EXPTIME-Complete.	LICS	1997	DBLP DOI BibTeX RDF
16	Pierluigi Crescenzi, Luca Trevisan	On Approximation Scheme Preserving Reducability and Its Applications.	FSTTCS	1994	DBLP DOI BibTeX RDF
16	Pekka Orponen	On the Computational Power of Discrete Hopfield Nets.	ICALP	1993	DBLP DOI BibTeX RDF
16	David Fernández-Baca, Giora Slutzki	Parametric Problems on Graphs of Bounded Tree-Width.	SWAT	1992	DBLP DOI BibTeX RDF
12	Aleksander Madry	Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms.	STOC	2010	DBLP DOI BibTeX RDF	dynamic graph algorithms, multicommodity flow problems
12	Peter Bürgisser	On Defining Integers And Proving Arithmetic Circuit Lower Bounds.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	Primary 68Q17, Secondary 11D45, Subject classification
12	Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen	Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem.	Algorithmica	2009	DBLP DOI BibTeX RDF	Random orthonormal measurement bases, Ensemble quantum state distinction, Hidden subgroup problem, Frobenius distance, Quantum Fourier transforms, Gel’fand pairs, Quantum algorithms
12	Leslie G. Valiant	Evolvability.	J. ACM	2009	DBLP DOI BibTeX RDF	SQ learning, Evolvable, PAC learning
12	Michel Abdalla, Dario Catalano, Dario Fiore 0001	Verifiable Random Functions from Identity-Based Key Encapsulation.	EUROCRYPT	2009	DBLP DOI BibTeX RDF
12	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the impact of combinatorial structure on congestion games.	J. ACM	2008	DBLP DOI BibTeX RDF	convergence, local search, Nash equilibria, Congestion games
12	Klaus Jansen, Ralf Thöle	Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2.	ICALP (1)	2008	DBLP DOI BibTeX RDF
12	Ran Canetti, Ling Cheung, Dilsun Kirli Kaynar, Nancy A. Lynch, Olivier Pereira	Modeling Computational Security in Long-Lived Systems.	CONCUR	2008	DBLP DOI BibTeX RDF
12	Ming-Yung Ko, Praveen K. Murthy, Shuvra S. Bhattacharyya	Beyond single-appearance schedules: Efficient DSP software synthesis using nested procedure calls.	ACM Trans. Embed. Comput. Syst.	2007	DBLP DOI BibTeX RDF	block diagram compiler, hierarchical graph decomposition, procedural implementation, embedded systems, design methodology, memory optimization, Synchronous dataflow
12	Rhydian Lewis	On the Combination of Constraint Programming and Stochastic Search: The Sudoku Case.	Hybrid Metaheuristics	2007	DBLP DOI BibTeX RDF
12	Guillaume Bonfante, Jean-Yves Marion, Romain Péchoux	Quasi-interpretation Synthesis by Decomposition.	ICTAC	2007	DBLP DOI BibTeX RDF
12	Roberto Segala, Andrea Turrini	Approximated Computationally Bounded Simulation Relations for Probabilistic Automata.	CSF	2007	DBLP DOI BibTeX RDF
12	Peter Bürgisser	On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds.	STACS	2007	DBLP DOI BibTeX RDF
12	Olaf Beyersdorff	The Deduction Theorem for Strong Propositional Proof Systems.	FSTTCS	2007	DBLP DOI BibTeX RDF
12	Francesco M. Malvestuto, Mauro Mezzini, Marina Moscarini	Auditing sum-queries to make a statistical database secure.	ACM Trans. Inf. Syst. Secur.	2006	DBLP DOI BibTeX RDF	Additive data, sensitive information
12	Jin-yi Cai, Osamu Watanabe 0001	Random Access to Advice Strings and Collapsing Results.	Algorithmica	2006	DBLP DOI BibTeX RDF
12	Marcus Tressl	Pseudo completions and completions in stages of o-minimal structures.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) Primary 03C64, Primary 12J10, Primary 12J15, Secondary 13B35
12	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the Impact of Combinatorial Structure on Congestion Games.	FOCS	2006	DBLP DOI BibTeX RDF
12	Aurélien Lemay, Joachim Niehren, Rémi Gilleron	Learning n-Ary Node Selecting Tree Transducers from Completely Annotated Examples.	ICGI	2006	DBLP DOI BibTeX RDF
12	Jean-Yves Marion, Romain Péchoux	Resource Analysis by Sup-interpretation.	FLOPS	2006	DBLP DOI BibTeX RDF
12	Anne Berry, Ross M. McConnell, Alain Sigayret, Jeremy P. Spinrad	Very Fast Instances for Concept Generation.	ICFCA	2006	DBLP DOI BibTeX RDF
12	Jiejun Kong, Xiaoyan Hong, Mario Gerla	Modeling Ad-hoc rushing attack in a negligibility-based security framework.	Workshop on Wireless Security	2006	DBLP DOI BibTeX RDF	asymptotic invariant, neg-ligibility, randomized network algorithms, randomized turing machine, sub-polynomial, scalability
12	Pranab Sen	Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem.	CCC	2006	DBLP DOI BibTeX RDF
12	Ittai Abraham, Cyril Gavoille, Dahlia Malkhi	On space-stretch trade-offs: upper bounds.	SPAA	2006	DBLP DOI BibTeX RDF	compact routing
12	Niranjan Ratnakar, Ralf Koetter	Exponential error bounds for algebraic soft-decision decoding of Reed-Solomon codes.	IEEE Trans. Inf. Theory	2005	DBLP DOI BibTeX RDF
12	László Babai, Thomas P. Hayes	Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group.	SODA	2005	DBLP BibTeX RDF
12	Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid	Fast Pruning of Geometric Spanners.	STACS	2005	DBLP DOI BibTeX RDF
12	Fabian Kuhn, Tim Nieberg, Thomas Moscibroda, Roger Wattenhofer	Local approximation schemes for ad hoc and sensor networks.	DIALM-POMC	2005	DBLP DOI BibTeX RDF	distributed algorithm, approximation, wireless ad hoc networks, maximum independent set, minimum dominating set
12	Alin Bostan, Thomas Cluzeau, Bruno Salvy	Fast algorithms for polynomial solutions of linear differential equations.	ISSAC	2005	DBLP DOI BibTeX RDF	complexity, computer algebra, linear recurrences, linear differential equations, polynomial solutions
12	Peter Bürgisser	The Complexity of Factors of Multivariate Polynomials.	Found. Comput. Math.	2004	DBLP DOI BibTeX RDF