BibSLEIGH
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
Used together with:
time (177)
algorithm (69)
approxim (39)
comput (34)
problem (34)

Stem polynomi$ (all stems)

444 papers:

VLDBVLDB-2015-BidoitHT #named
EFQ: Why-Not Answer Polynomials in Action (NB, MH, KT), pp. 1980–1991.
SASSAS-2015-AdjeGM #generative #invariant #optimisation #polynomial #using
Property-based Polynomial Invariant Generation Using Sums-of-Squares Optimization (AA, PLG, VM), pp. 235–251.
STOCSTOC-2015-AbrahamD #complexity #polynomial
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity (IA, DD), pp. 605–614.
STOCSTOC-2015-DinurHK #composition #fault #query
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition (ID, PH, GK), pp. 267–276.
STOCSTOC-2015-DvirG #communication
2-Server PIR with Sub-Polynomial Communication (ZD, SG), pp. 577–584.
STOCSTOC-2015-FoxKM #approximate #polynomial
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection (KF, PNK, SM), pp. 841–850.
ICALPICALP-v1-2015-FominKLPS #algorithm #polynomial
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree (FVF, PK, DL, FP, SS), pp. 494–505.
ICALPICALP-v1-2015-Ganguly #polynomial
Taylor Polynomial Estimator for Estimating Frequency Moments (SG), pp. 542–553.
ICALPICALP-v1-2015-GaspersS #algorithm #performance #set
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets (SG, GBS), pp. 567–579.
ICALPICALP-v2-2015-EtessamiSY #branch #equation #fixpoint #markov #polynomial #probability #process #reachability
Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes (KE, AS, MY), pp. 184–196.
ICALPICALP-v2-2015-JurdzinskiLS #energy #game studies #pseudo
Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time (MJ, RL, SS), pp. 260–272.
LATALATA-2015-AmanoS #bound #multi #polynomial
A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP (KA, AS), pp. 461–472.
CAVCAV-2015-ChenHWZ #generative #invariant #polynomial
Counterexample-Guided Polynomial Loop Invariant Generation by Lagrange Interpolation (YFC, CDH, BYW, LZ), pp. 658–674.
CSLCSL-2015-GasconST #polynomial #strict #unification
Two-Restricted One Context Unification is in Polynomial Time (AG, MSS, AT), pp. 405–422.
LICSLICS-2015-GasconTS #polynomial #problem #unification
One Context Unification Problems Solvable in Polynomial Time (AG, AT, MSS), pp. 499–510.
LICSLICS-2015-GradelPSK #first-order #polynomial
Characterising Choiceless Polynomial Time with First-Order Interpretations (EG, WP, SS, LK), pp. 677–688.
TLCATLCA-2015-Redmond #parametricity #polynomial #λ-calculus
Polynomial Time in the Parametric λ Calculus (BFR), pp. 288–301.
ASEASE-2014-ZhangCHXXZM #polynomial #search-based
Search-based inference of polynomial metamorphic relations (JZ, JC, DH, YX, BX, LZ, HM), pp. 701–712.
DACDAC-2014-WangOC #optimisation #performance #polynomial #synthesis
Enabling Efficient Analog Synthesis by Coupling Sparse Regression and Polynomial Optimization (YW, MO, CC), p. 6.
SASSAS-2014-GhorbalSP #algebra #difference #equation #polynomial
Invariance of Conjunctions of Polynomial Equalities for Algebraic Differential Equations (KG, AS, AP), pp. 151–167.
STOCSTOC-2014-ChanDSS #approximate #estimation #performance #polynomial
Efficient density estimation via piecewise polynomial approximation (SoC, ID, RAS, XS), pp. 604–613.
STOCSTOC-2014-ChekuriC #bound #polynomial #theorem
Polynomial bounds for the grid-minor theorem (CC, JC), pp. 60–69.
STOCSTOC-2014-DeS #approximate #performance #polynomial
Efficient deterministic approximate counting for low-degree polynomial threshold functions (AD, RAS), pp. 832–841.
STOCSTOC-2014-KayalLSS #bound
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas (NK, NL, CS, SS), pp. 119–127.
STOCSTOC-2014-KayalSS #bound
A super-polynomial lower bound for regular arithmetic formulas (NK, CS, RS), pp. 146–153.
STOCSTOC-2014-Vegh #algorithm #polynomial
A strongly polynomial algorithm for generalized flow maximization (LAV), pp. 644–653.
ICALPICALP-v1-2014-AllamigeonBG #algorithm #game studies #polynomial
The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average (XA, PB, SG), pp. 89–100.
ICALPICALP-v1-2014-BjorklundH #polynomial
Shortest Two Disjoint Paths in Polynomial Time (AB, TH), pp. 211–222.
ICALPICALP-v1-2014-DvirOS #equivalence #testing
Testing Equivalence of Polynomials under Shifts (ZD, RMdO, AS), pp. 417–428.
ICALPICALP-v1-2014-KoppartyKS #finite #performance
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields (SK, MK, MES), pp. 726–737.
ICMLICML-c2-2014-AndoniPV0 #learning #network
Learning Polynomials with Neural Networks (AA, RP, GV, LZ), pp. 1908–1916.
KRKR-2014-GottlobMP #polynomial
Polynomial Combined Rewritings for Existential Rules (GG, MM, AP).
LOPSTRLOPSTR-2014-ChowdhuryLCKY #approximate #case study #logic programming #polynomial #semantics #source code
Polynomial Approximation to Well-Founded Semantics for Logic Programs with Generalized Atoms: Case Studies (MSC, FL, WC, AK, JHY), pp. 279–296.
RTARTA-TLCA-2014-CarvalhoS #decidability #polynomial #set
An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting (DdC, JGS), pp. 179–193.
ICSTSAT-2014-LarrazORR #constraints #polynomial
Minimal-Model-Guided Approaches to Solving Polynomial Constraints and Extensions (DL, AO, ERC, AR), pp. 333–350.
SMTSMT-2014-KhanhTO #difference #named #polynomial #smt
raSAT: SMT for Polynomial Inequality (TVK, VXT, MO), p. 67.
VMCAIVMCAI-2014-LeikeT #polynomial #source code #synthesis
Synthesis for Polynomial Lasso Programs (JL, AT), pp. 434–452.
CASECASE-2013-YueH13a #assembly #concurrent #petri net #policy #polynomial #process
A polynomial deadlock avoidance policy for a class of assembly processes based on Petri nets (HY, HH), pp. 1151–1156.
STOCSTOC-2013-AgrawalSS
Quasi-polynomial hitting-set for set-depth-Δ formulas (MA, CS, NS), pp. 321–330.
STOCSTOC-2013-BeckNT #calculus #polynomial #trade-off
Some trade-off results for polynomial calculus: extended abstract (CB, JN, BT), pp. 813–822.
STOCSTOC-2013-CadekKMVW
Extending continuous maps: polynomiality and undecidability (MC, MK, JM, LV, UW), pp. 595–604.
STOCSTOC-2013-KaneM
A PRG for lipschitz functions of polynomials with applications to sparsest cut (DMK, RM), pp. 1–10.
STOCSTOC-2013-KeevashKM #polynomial
Polynomial-time perfect matchings in dense hypergraphs (PK, FK, RM), pp. 311–320.
STOCSTOC-2013-KingS #polynomial
Byzantine agreement in polynomial expected time: [extended abstract] (VK, JS), pp. 401–410.
DLTDLT-2013-FeliceN #algorithm #automaton
Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata (SDF, CN), pp. 179–190.
DLTDLT-2013-Pin #regular expression
An Explicit Formula for the Intersection of Two Polynomials of Regular Languages (JÉP), pp. 31–45.
ICALPICALP-v1-2013-BorosEGM #algorithm #game studies #probability #pseudo #random
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions (EB, KME, VG, KM), pp. 220–231.
ICALPICALP-v1-2013-BulanekKS #on the #online #random
On Randomized Online Labeling with Polynomially Many Labels (JB, MK, MES), pp. 291–302.
ICALPICALP-v1-2013-DuanM #algorithm #combinator #linear #polynomial
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market (RD, KM), pp. 425–436.
ICALPICALP-v1-2013-FilmusLMNV #bound #calculus #comprehension #polynomial #towards
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds — (Extended Abstract) (YF, ML, MM, JN, MV), pp. 437–448.
ICALPICALP-v1-2013-GlasserNRSW #polynomial #reduction #set
Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions (CG, DTN, CR, ALS, MW), pp. 473–484.
ICALPICALP-v1-2013-GolovachHKV #algorithm #incremental #polynomial #set
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets (PAG, PH, DK, YV), pp. 485–496.
ICALPICALP-v1-2013-JansenK #migration #online #polynomial #robust
A Robust AFPTAS for Online Bin Packing with Polynomial Migration, (KJ, KMK), pp. 589–600.
ICALPICALP-v1-2013-LeviR #graph
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor (RL, DR), pp. 709–720.
ICALPICALP-v2-2013-ChristodoulouG #game studies #polynomial
Price of Stability in Polynomial Congestion Games (GC, MG), pp. 496–507.
ICALPICALP-v2-2013-DieudonneP #approach #polynomial
Deterministic Polynomial Approach in the Plane (YD, AP), pp. 533–544.
ICALPICALP-v2-2013-Woods #generative
Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials (KW), pp. 410–421.
LATALATA-2013-Blanchet-SadriBFH #approach #graph #polynomial
A Graph Polynomial Approach to Primitivity (FBS, MB, NF, JH), pp. 153–164.
KDDKDD-2013-PhamP #kernel #performance #polynomial #scalability
Fast and scalable polynomial kernels via explicit feature maps (NP, RP), pp. 239–247.
PPDPPPDP-2013-YamadaKS #order #polynomial #recursion
Unifying the Knuth-Bendix, recursive path and polynomial orders (AY, KK, TS), pp. 181–192.
SACSAC-2013-RabanalR #metaheuristic #polynomial #problem #reduction #using
Using polynomial reductions to test the suitability of metaheuristics for solving NP-complete problems (PR, IR), pp. 194–199.
CCCC-2013-Krause #polynomial
Optimal Register Allocation in Polynomial Time (PKK), pp. 1–20.
CGOCGO-2013-DioufCR #heuristic #polynomial
A polynomial spilling heuristic: Layered allocation (BD, AC, FR), p. 10.
CADECADE-2013-KovasznaiFB #quantifier
: A Tool for Polynomially Translating Quantifier-Free Bit-Vector Formulas into (GK, AF, AB), pp. 443–449.
CAVCAV-2013-ChengRS #constraints #named #polynomial
JBernstein: A Validity Checker for Generalized Polynomial Constraints (CHC, HR, NS), pp. 656–661.
CAVCAV-2013-PuggelliLSS #nondeterminism #polynomial #verification
Polynomial-Time Verification of PCTL Properties of MDPs with Convex Uncertainties (AP, WL, ALSV, SAS), pp. 527–542.
CAVCAV-2013-StewartEY #automaton #bound #model checking #polynomial #probability
Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata (AS, KE, MY), pp. 495–510.
CASECASE-2012-ChenK #polynomial #probability
Polynomial test for Stochastic Diagnosability of discrete event systems (JC, RK), pp. 521–526.
PEPMPEPM-2012-MatsudaIN #cumulative #multi #polynomial #traversal
Polynomial-time inverse computation for accumulative functions with multiple data traversals (KM, KI, KN), pp. 5–14.
SASSAS-2012-CacheraJJK #imperative #invariant #polynomial #source code
Inference of Polynomial Invariants for Imperative Programs: A Farewell to Gröbner Bases (DC, TPJ, AJ, FK), pp. 58–74.
STOCSTOC-2012-BartalGK #approximate #polynomial #problem
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme (YB, LAG, RK), pp. 663–672.
STOCSTOC-2012-EtessamiSY #algorithm #branch #context-free grammar #multi #polynomial #probability #process
Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars (KE, AS, MY), pp. 579–588.
STOCSTOC-2012-Kayal
Affine projections of polynomials: extended abstract (NK), pp. 643–662.
STOCSTOC-2012-Sherstov12a #robust
Making polynomials robust to noise (AAS), pp. 747–758.
STOCSTOC-2012-Vegh #algorithm #low cost #polynomial #problem
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives (LAV), pp. 27–40.
ICALPICALP-v1-2012-BabaiCQ #morphism #polynomial
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups — (Extended Abstract) (LB, PC, YQ), pp. 51–62.
ICALPICALP-v1-2012-EtessamiSY #algorithm #branch #equation #markov #polynomial #probability #process
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations (KE, AS, MY), pp. 314–326.
ICALPICALP-v1-2012-GoldbergJ #approximate #complexity #polynomial
The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation) (LAG, MJ), pp. 399–410.
ICALPICALP-v1-2012-PolacekS #strict
Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation (LP, OS), pp. 726–737.
ICALPICALP-v2-2012-Fiore #polynomial
Discrete Generalised Polynomial Functors — (Extended Abstract) (MPF), pp. 214–226.
LATALATA-2012-GeilkeZ #algorithm #learning #pattern matching #polynomial
Polynomial-Time Algorithms for Learning Typed Pattern Languages (MG, SZ), pp. 277–288.
ICPRICPR-2012-AskKA #equation #performance #polynomial #symmetry
Exploiting p-fold symmetries for faster polynomial equation solving (EA, YK, ), pp. 3232–3235.
PPDPPPDP-2012-Madet #multi #polynomial #thread #λ-calculus
A polynomial time λ-calculus with multithreading and side effects (AM), pp. 55–66.
POPLPOPL-2012-SmaragdakisESYF #concurrent #detection #polynomial #predict
Sound predictive race detection in polynomial time (YS, JE, CS, JY, CF), pp. 387–400.
ICSEICSE-2012-NguyenKWF #array #dynamic analysis #invariant #polynomial #using
Using dynamic analysis to discover polynomial and array invariants (TN, DK, WW, SF), pp. 683–693.
ICSEICSE-2012-ZhouXZ #bound #named #polynomial #search-based
Stride: Search-based deterministic replay in polynomial time via bounded linkage (JZ, XX, CZ), pp. 892–902.
RTARTA-2012-FuhsK #higher-order #polynomial
Polynomial Interpretations for Higher-Order Rewriting (CF, CK), pp. 176–192.
ICSTSAT-2012-KatsirelosS #learning #satisfiability
Learning Polynomials over GF(2) in a SAT Solver — (Poster Presentation) (GK, LS), pp. 496–497.
DACDAC-2011-GongYH #analysis #monte carlo #orthogonal #performance #probability
Fast non-monte-carlo transient noise analysis for high-precision analog/RF circuits by stochastic orthogonal polynomials (FG, HY, LH), pp. 298–303.
ESOPESOP-2011-HuntS #exponential #polynomial #security #type system
From Exponential to Polynomial-Time Security Typing via Principal Types (SH, DS), pp. 297–316.
STOCSTOC-2011-AdsulGMS #algorithm #game studies #morphism #polynomial
Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm (BA, JG, RM, MAS), pp. 195–204.
DLTDLT-J-2010-RigoW11 #finite #logic #set
Logical Characterization of Recognizable Sets of polynomials over a Finite Field (MR, LW), pp. 1549–1563.
AFLAFL-2011-PramodK #polynomial #towards #word
Towards Shortest Synchronizing Words in Polynomial Time (VTKP, KVK), pp. 358–367.
ICALPICALP-v1-2011-GoldbergJ #algorithm #polynomial
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid (LAG, MJ), pp. 521–532.
ICALPICALP-v1-2011-JansenS #constant #polynomial
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth (MJJ, RS), pp. 724–735.
ICALPICALP-v1-2011-MakarychevS #constraints
Maximizing Polynomials Subject to Assignment Constraints (KM, MS), pp. 510–520.
FMFM-2011-DiosP #bound #certification #memory management #polynomial
Certification of Safe Polynomial Memory Bounds (JdD, RP), pp. 184–199.
HCIHCI-DDA-2011-ZhuYZ #polynomial
A Cubic Polynomial Model for Fisheye Camera (HZ, XY, JZ), pp. 684–693.
VLDBVLDB-2010-FanLMTWW #graph #pattern matching #polynomial
Graph Pattern Matching: From Intractable to Polynomial Time (WF, JL, SM, NT, YW, YW), pp. 264–275.
ESOPESOP-2010-HoffmannH #analysis #polynomial
Amortized Resource Analysis with Polynomial Potential (JH, MH), pp. 287–306.
STOCSTOC-2010-Aaronson #polynomial
BQP and the polynomial hierarchy (SA), pp. 141–150.
STOCSTOC-2010-BurgisserC #equation #polynomial #problem
Solving polynomial equations in smoothed polynomial time and a near solution to smale’s 17th problem (PB, FC), pp. 503–512.
STOCSTOC-2010-DellM #polynomial #satisfiability
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (HD, DvM), pp. 251–260.
STOCSTOC-2010-DiakonikolasHKMRST #bound #polynomial
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions (ID, PH, AK, RM, PR, RAS, LYT), pp. 533–542.
STOCSTOC-2010-HaramatyS #on the #polynomial
On the structure of cubic and quartic polynomials (EH, AS), pp. 331–340.
STOCSTOC-2010-MekaZ #generative #polynomial #pseudo
Pseudorandom generators for polynomial threshold functions (RM, DZ), pp. 427–436.
STOCSTOC-2010-Patrascu #bound #polynomial #problem #towards
Towards polynomial lower bounds for dynamic problems (MP), pp. 603–610.
STOCSTOC-2010-Sherstov #bound
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials (AAS), pp. 523–532.
DLTDLT-J-2008-GawrychowskiKRS10 #context-free grammar #polynomial
Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time (PG, DK, NR, JS), pp. 597–618.
CIAACIAA-2010-ReidenbachS #polynomial #regular expression #scalability
A Polynomial Time Match Test for Large Classes of Extended Regular Expressions (DR, MLS), pp. 241–250.
ICALPICALP-v1-2010-DellHW #complexity #exponential #polynomial
Exponential Time Complexity of the Permanent and the Tutte Polynomial (HD, TH, MW), pp. 426–437.
ICALPICALP-v1-2010-Ito #approximate #proving
Polynomial-Space Approximation of No-Signaling Provers (TI), pp. 140–151.
ICALPICALP-v1-2010-ShpilkaV #on the #polynomial #testing
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors (AS, IV), pp. 408–419.
ICALPICALP-v2-2010-Blum #lr #on the #polynomial
On LR(k)-Parsers of Polynomial Size (NB), pp. 163–174.
ICPRICPR-2010-PernekH #polynomial #problem #re-engineering
Perspective Reconstruction and Camera Auto-Calibration as Rectangular Polynomial Eigenvalue Problem (ÁP, LH), pp. 49–52.
SACSAC-2010-FunfzigMF #polynomial
Polytope-based computation of polynomial ranges (CF, DM, SF), pp. 1247–1252.
IJCARIJCAR-2010-NeurauterMZ #polynomial
Monotonicity Criteria for Polynomial Interpretations over the Naturals (FN, AM, HZ), pp. 502–517.
LICSLICS-2010-Grohe #fixpoint #graph #polynomial
Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors (MG), pp. 179–188.
LICSLICS-2010-Laubner #graph #polynomial
Capturing Polynomial Time on Interval Graphs (BL), pp. 199–208.
RTARTA-2010-NeurauterM #integer #polynomial
Polynomial Interpretations over the Reals do not Subsume Polynomial Interpretations over the Integers (FN, AM), pp. 243–258.
RTARTA-2010-Waldmann #bound #matrix
Polynomially Bounded Matrix Interpretations (JW), pp. 357–372.
DACDAC-2009-HuLA #approximate #polynomial
A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion (SH, ZL, CJA), pp. 424–429.
DACDAC-2009-SarbisheiAF #clustering #heuristic #optimisation #polynomial #using
Polynomial datapath optimization using partitioning and compensation heuristics (OS, BA, MF), pp. 931–936.
DATEDATE-2009-GopalakrishnanK #algebra #polynomial #synthesis
Algebraic techniques to enhance common sub-expression elimination for polynomial system synthesis (SG, PK), pp. 1452–1457.
DATEDATE-2009-WangCTHR #modelling #optimisation #performance #polynomial #using
An efficient decoupling capacitance optimization using piecewise polynomial models (XW, YC, SXDT, XH, JR), pp. 1190–1195.
PODSPODS-2009-Parys #complexity #evaluation #linear #polynomial #xpath
XPath evaluation in linear time with polynomial combined complexity (PP), pp. 55–64.
FoSSaCSFoSSaCS-2009-BonsangueRS #algebra #polynomial #theorem
A Kleene Theorem for Polynomial Coalgebras (MMB, JJMMR, AS), pp. 122–136.
STOCSTOC-2009-BabaiBS #matrix #polynomial
Polynomial-time theory of matrix groups (LB, RB, ÁS), pp. 55–64.
STOCSTOC-2009-Ben-SassonK
Affine dispersers from subspace polynomials (EBS, SK), pp. 65–74.
ICALPICALP-v1-2009-Nederlof #algorithm #performance #problem #using
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems (JN), pp. 713–725.
ICALPICALP-v2-2009-BrancoP #equation #polynomial #regular expression
Equations Defining the Polynomial Closure of a Lattice of Regular Languages (MJJB, JÉP), pp. 115–126.
FMFM-2009-SeidlVV #alias #analysis #linear #polynomial
A Smooth Combination of Linear and Herbrand Equalities for Polynomial Time Must-Alias Analysis (HS, VV, VV), pp. 644–659.
ICMLICML-2009-KolterN #polynomial
Near-Bayesian exploration in polynomial time (JZK, AYN), pp. 513–520.
ICMLICML-2009-SzitaL #learning #polynomial
Optimistic initialization and greediness lead to polynomial time learning in factored MDPs (IS, AL), pp. 1001–1008.
CADECADE-2009-BorrallerasLNRR #linear #polynomial #satisfiability
Solving Non-linear Polynomial Arithmetic via SAT Modulo Linear Arithmetic (CB, SL, RNM, ERC, AR), pp. 294–305.
CAVCAV-2009-DangS #image #polynomial #using
Image Computation for Polynomial Dynamical Systems Using the Bernstein Expansion (TD, DS), pp. 219–232.
CSLCSL-2009-Grohe #fixpoint #polynomial
Fixed-Point Definability and Polynomial Time (MG), pp. 20–23.
LICSLICS-2009-BonsangueRS #algebra #polynomial
An Algebra for Kripke Polynomial Coalgebras (MMB, JJMMR, AS), pp. 49–58.
RTARTA-2009-AvanziniM #dependence #order #polynomial
Dependency Pairs and Polynomial Path Orders (MA, GM), pp. 48–62.
CASECASE-2008-ChuCSC #algorithm #polynomial
An O(T3) Polynomial algorithm for crude oil transportation (FC, CC, QS, HC), pp. 303–308.
DACDAC-2008-QianR #logic #polynomial #probability #robust #synthesis
The synthesis of robust polynomial arithmetic with stochastic logic (WQ, MDR), pp. 648–653.
DATEDATE-2008-MasrurDF #polynomial #testing
Improvements in Polynomial-Time Feasibility Testing for EDF (AM, SD, GF), pp. 1033–1038.
SASSAS-2008-SeidlFP #equation #polynomial
Analysing All Polynomial Equations in ℤ₂ᵂ (HS, AF, MP), pp. 299–314.
STOCSTOC-2008-Lovett #generative #pseudo
Unconditional pseudorandom generators for low degree polynomials (SL), pp. 557–562.
STOCSTOC-2008-ShpilkaV #polynomial #testing
Read-once polynomial identity testing (AS, IV), pp. 507–516.
STOCSTOC-2008-Umans #composition #performance #polynomial
Fast polynomial factorization and modular composition in small characteristic (CU), pp. 481–490.
DLTDLT-2008-GawrychowskiKRS #context-free grammar #polynomial
Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time (PG, DK, NR, JS), pp. 339–358.
ICALPICALP-A-2008-BlaserHS #set
Asymptotically Optimal Hitting Sets Against Polynomials (MB, MH, DS), pp. 345–356.
ICALPICALP-A-2008-BodlaenderDFH #kernel #on the #polynomial #problem
On Problems without Polynomial Kernels (Extended Abstract) (HLB, RGD, MRF, DH), pp. 563–574.
ICALPICALP-A-2008-DiakonikolasLMSW #testing
Efficiently Testing Sparse GF(2) Polynomials (ID, HKL, KM, RAS, AW), pp. 502–514.
ICALPICALP-A-2008-EsparzaGKS #approximate #equation
Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations (JE, TG, SK, HS), pp. 698–710.
ICALPICALP-A-2008-FrandsenS #normalisation #polynomial
Dynamic Normal Forms and Dynamic Characteristic Polynomial (GSF, PS), pp. 434–446.
ICALPICALP-A-2008-IwamaNPRY #linear #network #polynomial
Polynomial-Time Construction of Linear Network Coding (KI, HN, MP, RR, SY), pp. 271–282.
ICALPICALP-B-2008-Chen #constraints #quantifier
Quantified Constraint Satisfaction and the Polynomially Generated Powers Property (HC), pp. 197–208.
SOFTVISSOFTVIS-2008-ThompsonPAH #polynomial #visualisation
Visualizing the computation tree of the Tutte Polynomial (BT, DJP, CA, GH), pp. 211–212.
ICPRICPR-2008-CheongL #approach #image #matrix #multi #orthogonal #recognition #using
An approach to texture-based image recognition by deconstructing multispectral co-occurrence matrices using Tchebichef orthogonal polynomials (MCYC, KSL), pp. 1–4.
PPDPPPDP-2008-MarionP #complexity #polynomial
Characterizations of polynomial complexity classes with a better intensionality (JYM, RP), pp. 79–88.
LICSLICS-2008-Riis #calculus #complexity #on the #polynomial #proving
On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity (SR), pp. 272–283.
DATEDATE-2007-BonziniP #automation #polynomial #set
Polynomial-time subgraph enumeration for automated instruction set extension (PB, LP), pp. 1331–1336.
PODSPODS-2007-FiliotNTT #polynomial #xpath
Polynomial time fragments of XPath with variables (EF, JN, JMT, ST), pp. 205–214.
FoSSaCSFoSSaCS-2007-MarnetteKR #bound #constraints #polynomial #set
Polynomial Constraints for Sets with Cardinality Bounds (BM, VK, MCR), pp. 258–273.
STOCSTOC-2007-ChuzhoyK #polynomial #problem
Polynomial flow-cut gaps and hardness of directed cut problems (JC, SK), pp. 179–188.
STOCSTOC-2007-GoldbergJ #polynomial
Inapproximability of the Tutte polynomial (LAG, MJ), pp. 459–468.
STOCSTOC-2007-HavivR #polynomial #problem
Tensor-based hardness of the shortest vector problem to within almost polynomial factors (IH, OR), pp. 469–477.
STOCSTOC-2007-KieferLE #convergence #equation #on the #polynomial
On the convergence of Newton’s method for monotone systems of polynomial equations (SK, ML, JE), pp. 217–226.
CIAACIAA-J-2006-BastienCFR07 #exponential
Reducing Simple Grammars: Exponential against Highly-Polynomial Time in Practice (CB, JC, WF, WR), pp. 715–725.
ICALPICALP-2007-BlaserD #complexity #polynomial
Complexity of the Cover Polynomial (MB, HD), pp. 801–812.
PPDPPPDP-2007-Lucas #proving #termination
Practical use of polynomials over the reals in proofs of termination (SL), pp. 39–50.
ICSTSAT-2007-Buresh-OppenheimM #polynomial
Minimum 2CNF Resolution Refutations in Polynomial Time (JBO, DGM), pp. 300–313.
ICSTSAT-2007-FuhsGMSTZ #analysis #polynomial #satisfiability #termination
SAT Solving for Termination Analysis with Polynomial Interpretations (CF, JG, AM, PSK, RT, HZ), pp. 340–354.
ICSTSAT-2007-Kullmann #invariant #matrix #polynomial #satisfiability
Polynomial Time SAT Decision for Complementation-Invariant Clause-Sets, and Sign-non-Singular Matrices (OK), pp. 314–327.
TLCATLCA-2007-Baillot #linear #logic #polynomial #type system
From Proof-Nets to Linear Logic Type Systems for Polynomial Time Computing (PB), pp. 2–7.
TLCATLCA-2007-ShkaravskaKE #analysis #first-order #polynomial
Polynomial Size Analysis of First-Order Functions (OS, RvK, MCJDvE), pp. 351–365.
CASECASE-2006-LopatinY #algorithm #approximate #polynomial #using
Using the forward search and the polynomial approximation algorithms in the exact algorithm for manipulator’s control in an unknown environment (PKL, ASY), pp. 206–211.
CASECASE-2006-XingTXH #complexity #concurrent #flexibility #policy #polynomial
Optimal Polynomial Complexity Deadlock Avoidance Policies for Manufacturing Systems with Flexible Routings (KX, FT, HX, BH), pp. 448–453.
PODSPODS-2006-GottlobN #polynomial
Data exchange: computing cores in polynomial time (GG, AN), pp. 40–49.
VLDBVLDB-2006-CohenFKKS
Full Disjunctions: Polynomial-Delay Iterators in Action (SC, IF, YK, BK, YS), pp. 739–750.
STOCSTOC-2006-AharonovJL #algorithm #approximate #polynomial #quantum
A polynomial quantum algorithm for approximating the Jones polynomial (DA, VJ, ZL), pp. 427–436.
STOCSTOC-2006-BarakRSW #graph
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction (BB, AR, RS, AW), pp. 671–680.
STOCSTOC-2006-Gurvits #algorithm #approach #bound #proving
Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications (LG), pp. 417–426.
STOCSTOC-2006-KelnerS #algorithm #linear #polynomial #programming #random
A randomized polynomial-time simplex algorithm for linear programming (JAK, DAS), pp. 51–60.
STOCSTOC-2006-Rao #constant #independence
Extractors for a constant number of polynomially small min-entropy independent sources (AR), pp. 497–506.
STOCSTOC-2006-RemyS #approximate
A quasi-polynomial time approximation scheme for minimum weight triangulation (JR, AS), pp. 316–325.
CIAACIAA-2006-BastienCFR #exponential
Reducing Simple Grammars: Exponential Against Highly-Polynomial Time in Practice (CB, JC, WF, WR), pp. 90–101.
DLTDLT-2006-GlasserTW #polynomial
Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy (CG, SDT, KWW), pp. 408–419.
DLTDLT-2006-Kufleitner #logic
Polynomials, Fragments of Temporal Logic and the Variety DA over Traces (MK), pp. 37–48.
ICALPICALP-v2-2006-KariantoKT #on the #problem #set
On Intersection Problems for Polynomially Generated Sets (KW, AK, WT), pp. 516–527.
KDDKDD-2006-Jaroszewicz #polynomial
Polynomial association rules with applications to logistic regression (SJ), pp. 586–591.
LOPSTRLOPSTR-2006-NguyenS #automation #named #polynomial #proving #termination
Polytool: Proving Termination Automatically Based on Polynomial Interpretations (MTN, DDS), pp. 210–218.
SACSAC-2006-BoldoM #evaluation
Provably faithful evaluation of polynomials (SB, CM), pp. 1328–1332.
SACSAC-2006-GraillatL #pseudo #set
Pseudozero set of interval polynomials (SG, PL), pp. 1655–1659.
CAVCAV-2006-RoyZFH #consistency #memory management #performance #polynomial #verification
Fast and Generalized Polynomial Time Memory Consistency Verification (AR, SZ, CJF, JCH), pp. 503–516.
IJCARIJCAR-2006-BaaderLS #named #ontology #polynomial
CEL — A Polynomial-Time Reasoner for Life Science Ontologies (FB, CL, BS), pp. 287–291.
IJCARIJCAR-2006-Mahboubi #algorithm #implementation #performance #proving
Proving Formally the Implementation of an Efficient gcd Algorithm for Polynomials (AM), pp. 438–452.
DATEDATE-2005-MartensG #integration #orthogonal #polynomial #simulation #using
Time-Domain Simulation of Sampled Weakly Nonlinear Systems Using Analytical Integration and Orthogonal Polynomial Series (EM, GGEG), pp. 120–125.
STOCSTOC-2005-Basu #algebra #algorithm #polynomial #set
Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities (SB), pp. 313–322.
STOCSTOC-2005-Bogdanov #generative #pseudo
Pseudorandom generators for low degree polynomials (AB), pp. 21–30.
STOCSTOC-2005-DvirS #polynomial #query #testing
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits (ZD, AS), pp. 592–601.
STOCSTOC-2005-SchmidtV #algorithm #polynomial #quantum
Polynomial time quantum algorithm for the computation of the unit group of a number field (AS, UV), pp. 475–480.
DLTDLT-J-2004-BorchertLSTT05 #polynomial
The dot-depth and the polynomial hierarchies correspond on the delta levels (BB, KJL, FS, PT, DT), pp. 625–644.
DLTDLT-2005-Kortelainen #generative #polynomial #recursion
Polynomial Generators of Recursively Enumerable Languages (JK), pp. 320–326.
ICALPICALP-2005-DattaDMST #logic #polynomial #probability #protocol #security #semantics
Probabilistic Polynomial-Time Semantics for a Protocol Security Logic (AD, AD, JCM, VS, MT), pp. 16–29.
ICALPICALP-2005-DiehlM #bound #polynomial #random
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines (SD, DvM), pp. 982–993.
ICALPICALP-2005-Kayal #equation #finite #polynomial
Solvability of a System of Bivariate Polynomial Equations over a Finite Field (NK), pp. 551–562.
ICALPICALP-2005-Kovacs #multi #polynomial
Polynomial Time Preemptive Sum-Multicoloring on Paths (AK), pp. 840–852.
ICSTSAT-J-2004-GalesiK05 #polynomial #rank #satisfiability
Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank (NG, OK), pp. 89–104.
CSLCSL-2005-SchurmannS #identification #polynomial #recursion
Identifying Polynomial-Time Recursive Functions (CS, JS), pp. 525–540.
ICLPICLP-2005-NguyenS #analysis #logic programming #polynomial #source code #termination
Polynomial Interpretations as a Basis for Termination Analysis of Logic Programs (MTN, DDS), pp. 311–325.
LICSLICS-2005-Leroux #diagrams #polynomial #synthesis
A Polynomial Time Presburger Criterion and Synthesis for Number Decision Diagrams (JL), pp. 147–156.
VMCAIVMCAI-2005-BradleyMS #polynomial #source code #termination
Termination of Polynomial Programs (ARB, ZM, HBS), pp. 113–129.
DATEDATE-v1-2004-RaudvereSSJ #abstraction #polynomial #verification
Polynomial Abstraction for Verification of Sequentially Implemented Combinational Circuits (TR, AKS, IS, AJ), pp. 690–691.
SIGMODSIGMOD-2004-NgC
Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials (YC, RTN), pp. 599–610.
FoSSaCSFoSSaCS-2004-BaillotM #polynomial #λ-calculus
Soft λ-Calculus: A Language for Polynomial Time Computation (PB, VM), pp. 27–41.
FoSSaCSFoSSaCS-2004-Lucas #proving #termination
Polynomials for Proving Termination of Context-Sensitive Rewriting (SL), pp. 318–332.
TACASTACAS-2004-SuW #analysis #constraints
A Class of Polynomially Solvable Range Constraints for Interval Analysis without Widenings and Narrowings (ZS, DW), pp. 280–295.
SASSAS-2004-GulwaniN #algorithm #polynomial
A Polynomial-Time Algorithm for Global Value Numbering (SG, GCN), pp. 212–227.
SASSAS-2004-Rodriguez-CarbonellK #abstract interpretation #approach #automation #generative #invariant #polynomial
An Abstract Interpretation Approach for Automatic Generation of Polynomial Invariants (ERC, DK), pp. 280–295.
STOCSTOC-2004-Ajtai #polynomial
A conjecture about polynomial time computable lattice-lattice functions (MA), pp. 486–493.
STOCSTOC-2004-DunaganV #algorithm #linear #polynomial #source code
A simple polynomial-time rescaling algorithm for solving linear programs (JD, SV), pp. 315–320.
STOCSTOC-2004-Raz #multi
Multi-linear formulas for permanent and determinant are of super-polynomial size (RR), pp. 633–641.
STOCSTOC-2004-SanthaS #quantum #query
Quantum and classical query complexities of local search are polynomially related (MS, MS), pp. 494–501.
DLTDLT-2004-BorchertLSTT #polynomial
The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels (BB, KJL, FS, PT, DT), pp. 89–101.
ICALPICALP-2004-Midrijanis #bound #polynomial #problem #quantum #query #set #similarity
A Polynomial Quantum Query Lower Bound for the Set Equality Problem (GM), pp. 996–1005.
ICMLICML-2004-BohteBG #classification #parametricity #polynomial
Nonparametric classification with polynomial MPMC cascades (SMB, MB, GZG).
ICPRICPR-v3-2004-DePiero #bound #graph #memory management #polynomial #worst-case
Structural Graph Matching With Polynomial Bounds On Memory and on Worst-Case Effort (FWD), pp. 379–382.
ICPRICPR-v3-2004-LuoWH #graph
Graph Manifolds from Spectral Polynomials (BL, RCW, ERH), pp. 402–405.
KRKR-2004-BaralE #algorithm #policy #polynomial
A Polynomial-Time Algorithm for Constructing k-Maintainable Policies (CB, TE), pp. 720–730.
SIGIRSIGIR-2004-KokiopoulouS #information retrieval #polynomial #semantics
Polynomial filtering in latent semantic indexing for information retrieval (EK, YS), pp. 104–111.
POPLPOPL-2004-Fiore #morphism #polynomial #recursion
Isomorphisms of generic recursive polynomial types (MPF), pp. 77–88.
LICSLICS-2004-BaillotT #polynomial #λ-calculus
Light Types for Polynomial Time Computation in λ-Calculus (PB, KT), pp. 266–275.
SATSAT-2004-GalesiK #polynomial #rank #satisfiability
Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank (NG, OK), pp. 76–85.
DACDAC-2003-DongR #polynomial #reduction
Piecewise polynomial nonlinear model reduction (ND, JSR), pp. 484–489.
FoSSaCSFoSSaCS-2003-BournezCNM #parallel #polynomial
Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time (OB, FC, PJdN, JYM), pp. 185–199.
STOCSTOC-2003-AzarCFKR #polynomial
Optimal oblivious routing in polynomial time (YA, EC, AF, HK, HR), pp. 383–388.
STOCSTOC-2003-BeierV #polynomial #random
Random knapsack in expected polynomial time (RB, BV), pp. 232–241.
STOCSTOC-2003-KabanetsI #bound #polynomial #proving #testing
Derandomizing polynomial identity tests means proving circuit lower bounds (VK, RI), pp. 355–364.
STOCSTOC-2003-ODonnellS #bound #polynomial
New degree bounds for polynomial threshold functions (RO, RAS), pp. 325–334.
FMFME-2003-MussetR #linear
Computing Meta-transitions for Linear Transition Systems with Polynomials (JM, MR), pp. 562–581.
CSLCSL-2003-KanovichV #problem
Coping Polynomially with Numerous but Identical Elements within Planning Problems (MIK, JV), pp. 285–298.
ICLPICLP-2003-Rao #polynomial
Polynomial-Time Learnability from Entailment (MRKKR), pp. 489–491.
LICSLICS-2003-Oliva #algorithm #effectiveness #polynomial #proving
Polynomial-time Algorithms from Ineffective Proofs (PO), pp. 128–137.
DATEDATE-2002-ChenBKR #reduction #using
Model Reduction in the Time-Domain Using Laguerre Polynomials and Krylov Methods (YC, VB, CKK, KR), pp. 931–935.
DATEDATE-2002-HuangTXWL #algorithm #polynomial #problem
A Polynomial Time Optimal Diode Insertion/Routing Algorithm for Fixing Antenna Problem (LDH, XT, HX, DFW, IML), pp. 470–475.
PLDIPLDI-2002-DasLS #named #polynomial #verification
ESP: Path-Sensitive Program Verification in Polynomial Time (MD, SL, MS), pp. 57–68.
SASSAS-2002-Lee #analysis #polynomial
Finiteness Analysis in Polynomial Time (CSL), pp. 493–508.
SASSAS-2002-Muller-OlmS #decidability #polynomial
Polynomial Constants Are Decidable (MMO, HS), pp. 4–19.
STOCSTOC-2002-BarakL #polynomial #simulation #strict
Strict polynomial-time in simulation and extraction (BB, YL), pp. 484–493.
STOCSTOC-2002-CryanD #algorithm #approximate #constant #polynomial
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant (MC, MED), pp. 240–249.
STOCSTOC-2002-Hallgren #algorithm #equation #polynomial #problem #quantum
Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem (SH), pp. 653–658.
CIAACIAA-2002-Trahtman #algorithm #polynomial #testing
A Polynomial Time Algorithm for Left [Right] Local Testability (ANT), pp. 203–212.
ICALPICALP-2002-CzumajLZ #approximate #design #network #polynomial #problem
Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem (AC, AL, HZ), pp. 973–984.
ICALPICALP-2002-ImpagliazzoS #axiom #bound #simulation
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations (RI, NS), pp. 208–219.
ICALPICALP-2002-IshaiK
Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials (YI, EK), pp. 244–256.
ICMLICML-2002-FitzgibbonDA #approximate #monte carlo #polynomial
Univariate Polynomial Inference by Monte Carlo Message Length Approximation (LJF, DLD, LA), pp. 147–154.
ICPRICPR-v2-2002-ErcilB #classification #polynomial #using
One Class Classification Using Implicit Polynomial Surface Fitting (AE, BB), pp. 152–155.
GPCEGPCE-2002-Lee #analysis #polynomial #termination
Program Termination Analysis in Polynomial Time (CSL), pp. 218–235.
ICLPICLP-2002-PearceSSTW #logic programming #polynomial #source code
A Polynomial Translation of Logic Programs with Nested Expressions into Disjunctive Logic Programs: Preliminary Report (DP, VS, TS, HT, SW), pp. 405–420.
LICSLICS-2002-Tiwari #confluence #polynomial #term rewriting
Deciding Confluence of Certain Term Rewriting Systems in Polynomial Time (AT), p. 447–?.
ESOPESOP-2001-Mitchell #analysis #calculus #polynomial #probability #process #protocol #security
Probabilistic Polynomial-Time Process Calculus and Security Protocol Analysis (JCM), pp. 23–29.
STOCSTOC-2001-JerrumSV #algorithm #approximate #matrix #polynomial
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (MJ, AS, EV), pp. 712–721.
STOCSTOC-2001-KlivansS #multi #performance #testing
Randomness efficient identity testing of multivariate polynomials (AK, DAS), pp. 216–223.
STOCSTOC-2001-Shparlinski #approximate #finite #polynomial
Sparse polynomial approximation in finite fields (IS), pp. 209–215.
STOCSTOC-2001-SpielmanT #algorithm #analysis #polynomial #why
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time (DAS, SHT), pp. 296–305.
STOCSTOC-2001-Valiant #polynomial #quantum
Quantum computers that can be simulated classically in polynomial time (LGV), pp. 114–123.
ICALPICALP-2001-KiayiasY #game studies #polynomial
Secure Games with Polynomial Expressions (AK, MY), pp. 939–950.
IFLIFL-2001-PenaS01a #analysis #nondeterminism
A Polynomial-Cost Non-determinism Analysis (RP, CS), pp. 121–137.
STOCSTOC-2000-GurvitsS #algorithm #approximate #polynomial
A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume (LG, AS), pp. 48–57.
STOCSTOC-2000-IwataFF #algorithm #combinator #polynomial
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions (SI, LF, SF), pp. 97–106.
STOCSTOC-2000-KenyonSY #approximate #polynomial
Polynomial-time approximation scheme for data broadcast (CK, NS, NEY), pp. 659–666.
STOCSTOC-2000-LiMW #multi #polynomial
Near optimal multiple alignment within a band in polynomial time (ML, BM, LW), pp. 425–434.
WLCWLC-2000-MargolisS #polynomial
Power Semigroups and Polynomial Closure (SWM, BS), pp. 311–322.
WLCWLC-2000-Nishio #automaton #finite
Cellular Automata with Polynomials over Finite Fields (HN), pp. 370–377.
ICMLICML-2000-CampbellTB #network #polynomial #reduction
Dimension Reduction Techniques for Training Polynomial Networks (WMC, KT, SVB), pp. 119–126.
ICPRICPR-v3-2000-HelzerBM #2d #robust
Robust Fitting of Implicit Polynomials with Quantized Coefficients to 2D Data (AH, MB, DM), pp. 3294–3297.
CSLCSL-2000-BlassG00a #polynomial
Choiceless Polynomial Time Computation and the Zero-One Law (AB, YG), pp. 18–40.
LICSLICS-2000-AehligS #analysis #polynomial
A Syntactical Analysis of Non-Size-Increasing Polynomial Time Computation (KA, HS), pp. 84–91.
DATEDATE-1999-SmithM #component #polynomial
Polynomial Methods for Allocating Complex Components (JS, GDM), pp. 217–222.
FoSSaCSFoSSaCS-1999-DantsinV #algorithm #nondeterminism #polynomial #set #unification
A Nondeterministic Polynomial-Time Unification Algorithm for Bags, Sets and Trees (ED, AV), pp. 180–196.
STOCSTOC-1999-BussGIP #calculus #linear #polynomial
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (SRB, DG, RI, TP), pp. 547–556.
STOCSTOC-1999-CaiNS #probability #theorem
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time (JyC, AN, DS), pp. 726–735.
STOCSTOC-1999-ChenM #approximate #multi #polynomial #scheduling
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract) (JC, AM), pp. 418–427.
STOCSTOC-1999-DinurFKRS #towards
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (ID, EF, GK, RR, SS), pp. 29–40.
STOCSTOC-1999-JansenSS #approximate #polynomial
Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme (KJ, RSO, MS), pp. 394–399.
STOCSTOC-1999-KlivansM #graph #morphism #polynomial #proving
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (AK, DvM), pp. 659–667.
STOCSTOC-1999-NaorP #evaluation #polynomial
Oblivious Transfer and Polynomial Evaluation (MN, BP), pp. 245–254.
STOCSTOC-1999-Schaefer #graph #polynomial
Graph Ramsey Theory and the Polynomial Hierarchy (MS), pp. 592–601.
STOCSTOC-1999-Wayne #algorithm #combinator #polynomial
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow (KDW), pp. 11–18.
ICALPICALP-1999-OlshevskyP #evaluation #matrix #polynomial
Polynomial and Rational Evaluation and Interpolation (with Structured Matrices) (VO, VYP), pp. 585–594.
FMFM-v1-1999-LincolnMMS #analysis #equivalence #polynomial #probability #security
Probabilistic Polynomial-Time Equivalence and Security Analysis (PL, JCM, MM, AS), pp. 776–793.
ICMLICML-1999-ParekhH #automaton
Simple DFA are Polynomially Probably Exactly Learnable from Simple Examples (RP, VH), pp. 298–306.
LICSLICS-1999-Hofmann99a #linear #polynomial
Linear Types and Non-Size-Increasing Polynomial Time Computation (MH0), pp. 464–473.
RTARTA-1999-Gobel #performance #symmetry
Fast Rewriting of Symmetric Polynomials (MG), pp. 371–381.
DATEDATE-1998-ChuW #algorithm #polynomial
A Polynomial Time Optimal Algorithm for Simultaneous Buffer and Wire Sizing (CCNC, DFW), pp. 479–485.
STOCSTOC-1998-LewinV #polynomial #question #towards
Checking Polynomial Identities over any Field: Towards a Derandomization? (DL, SPV), pp. 438–447.
STOCSTOC-1998-LinialSW #algorithm #approximate #matrix #polynomial #scalability
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents (NL, AS, AW), pp. 644–652.
STOCSTOC-1998-MourrainP #equation #multi #polynomial
Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations (BM, VYP), pp. 488–496.
STOCSTOC-1998-NatanzonSS #algorithm #approximate #polynomial #problem
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem (AN, RS, RS), pp. 41–47.
ICALPICALP-1998-CzumajL #approximate #polynomial
A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity (AC, AL), pp. 682–694.
ICALPICALP-1998-DyerG #algorithm #polynomial
A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables (MED, CSG), pp. 339–350.
CSLCSL-1998-BonfanteCMT #complexity #polynomial #term rewriting
Complexity Classes and Rewrite Systems with Polynomial Interpretation (GB, AC, JYM, HT), pp. 372–384.
ICDARICDAR-1997-FrankeGKM #classification #comparison #markov #modelling #polynomial #recognition
A Comparison of Gaussian Distribution and Polynomial Classifiers in a Hidden Markov Model Based System for the Recognition of Cursive Script (JF, JMG, AK, EM), pp. 515–518.
SASSAS-1997-Braunburger #analysis #automation #order #polynomial #termination #using
Automatic Termination Analysis for Partial Functions Using Polynomial Orderings (JB), pp. 330–344.
SASSAS-1997-Frey #polynomial #type system
Satisfying Subtype Inequalities in Polynomial Space (AF), pp. 265–277.
STOCSTOC-1997-AsanoKTT #approximate #polynomial #towards
Covering Points in the Plane by k-Tours: Towards a Polynomial Time Approximation Scheme for General k (TA, NK, HT, TT), pp. 275–283.
STOCSTOC-1997-Reif #approximate #constant #evaluation #polynomial
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point (JHR), pp. 30–39.
ICALPICALP-1997-CodenottiEGK
Checking Properties of Polynomials (Extended Abstract) (BC, FE, PG, RK), pp. 203–213.
ICMLICML-1997-MooreSD #performance #polynomial #predict
Efficient Locally Weighted Polynomial Regression Predictions (AWM, JGS, KD), pp. 236–244.
SACSAC-1997-FeinsilverGS #approach #on the #polynomial
On the computation of polynomial representations of nilpotent Lie groups: a symbolic mathematical approach (PF, UG, RS), pp. 537–539.
RTARTA-1997-BachmairT #commutative #polynomial
D-Bases for Polynomial Ideals over Commutative Noetherian Rings (LB, AT), pp. 113–127.
SASSAS-1996-Givan #polynomial #specification
Inferring Program Specifications in Polynomial-Time (RG), pp. 205–219.
ICALPICALP-1996-Fernandez-BacaL #algorithm #polynomial
A Polynomial-Time Algorithm for Near-Perfect Phylogeny (DFB, JL), pp. 670–680.
ICALPICALP-1996-FlajoletGP #polynomial #random
Random Polynomials and Polynomial Factorization (PF, XG, DP), pp. 232–243.
ICPRICPR-1996-Molina-GamezS #approach #polynomial #recognition
Sparse groups: A polynomial middle-level approach for object recognition (MCMG, JBSV), pp. 518–522.
CADECADE-1996-HermannK #algorithm #polynomial #unification
Unification Algorithms Cannot be Combined in Polynomial Time (MH, PGK), pp. 246–260.
CAVCAV-1996-Baier #algorithm #bisimulation #polynomial #probability #simulation #testing
Polynomial Time Algorithms for Testing Probabilistic Bisimulation and Simulation (CB), pp. 50–61.
LICSLICS-1996-Narendran #equation #linear #polynomial
Solving Linear Equations over Polynomial Semirings (PN), pp. 466–472.
SASSAS-1995-DussartHM #analysis #polymorphism #polynomial #recursion #type system
Polymorphic Recursion and Subtype Qualifications: Polymorphic Binding-Time Analysis in Polynomial Time (DD, FH, CM), pp. 118–135.
STOCSTOC-1995-AroraKK #approximate #np-hard #polynomial #problem
Polynomial time approximation schemes for dense instances of NP-hard problems (SA, DRK, MK), pp. 284–293.
STOCSTOC-1995-HannenhalliP #algorithm #permutation #polynomial #sorting
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals (SH, PAP), pp. 178–189.
STOCSTOC-1995-KaltofenS #finite
Subquadratic-time factoring of polynomials over finite fields (EK, VS), pp. 398–406.
STOCSTOC-1995-Karger #approximate #network #polynomial #problem #random #reliability
A randomized fully polynomial time approximation scheme for the all terminal network reliability problem (DRK), pp. 11–17.
STOCSTOC-1995-KarpinskiM #bound #network #polynomial
Polynomial bounds for VC dimension of sigmoidal neural networks (MK, AM), pp. 200–208.
STOCSTOC-1995-KushilevitzOR #communication #polynomial
Log-space polynomial end-to-end communication (EK, RO, AR), pp. 559–568.
STOCSTOC-1995-Pan #algorithm #approximate #parallel #polynomial
Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros (VYP), pp. 741–750.
STOCSTOC-1995-Reif #parallel #performance #polynomial
Work efficient parallel solution of Toeplitz systems and polynomial GCD (JHR), pp. 751–761.
ICALPICALP-1995-Ambos-Spies #approximate #on the #polynomial
On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (Extended Abstract) (KAS), pp. 384–392.
ICALPICALP-1995-PinW #ambiguity #polynomial
Polynomial Closure and Unambiguous Product (JÉP, PW), pp. 348–359.
CAVCAV-1995-Lescow #finite #game studies #on the #source code
On Polynomial-Size Programs Winning Finite-State Games (HL), pp. 239–252.
RTARTA-1995-Giesl #generative #order #polynomial #proving #termination
Generating Polynomial Orderings for Termination Proofs (JG), pp. 426–431.
RTARTA-1995-Senizergues #algorithm #confluence #polynomial #testing
A Polynomial Algorithm Testing Partial Confluence of Basic Semi-Thue Systems (GS), pp. 194–209.
ICALPICALP-1994-HoftingW #analysis #graph #polynomial
Polynomial Time Analysis of Torodial Periodic Graphs (FH, EW), pp. 544–555.
ICALPICALP-1994-Pin #polynomial #set
Polynomial Closure of Group Languages and Open Sets of the Hall Topology (JÉP), pp. 424–435.
SACSAC-1994-InsallMW #finite
Conjugating polynomials on finite rings (MI, LM, RWW), pp. 277–280.
DACDAC-1993-HuangPS #approach #approximate #heuristic #polynomial #problem
A Polynomial-Time Heuristic Approach to Approximate a Solution to the False Path Problem (STH, TMP, JMS), pp. 118–122.
DACDAC-1993-LiaoDWC #metaprogramming #network #polynomial #using
S-Parameter Based Macro Model of Distributed-Lumped Networks Using Exponentially Decayed Polynomial Function (HL, WWMD, RW, FYC), pp. 726–731.
STOCSTOC-1993-GarayM #polynomial
Fully polynomial Byzantine agreement in t+1 rounds (JAG, YM), pp. 31–41.
STOCSTOC-1993-Goldberg #algorithm #graph #polynomial #product line
Polynomial space polynomial delay algorithms for listing families of graphs (LAG), pp. 218–225.
STOCSTOC-1993-Shamir #generative #multi #on the
On the generation of multivariate polynomials which are hard to factor (AS), pp. 796–804.
ICALPICALP-1993-Kann #approximate #bound #problem
Polynomially Bounded Minimization Problems which are Hard to Approximate (VK), pp. 52–63.
ICALPICALP-1993-Schonhage #adaptation #finite #parallel #performance
Fast Parallel Computation of Characteristic Polynomials by Leverrier’s POwer Sum Method Adapted to Fields of Finite Characteristic (AS), pp. 410–417.
RTARTA-1993-Plaisted #constraints #polynomial #termination #testing
Polynomial Time Termination and Constraint Satisfaction Tests (DAP), pp. 405–420.
STOCSTOC-1992-AdlerB #algebra #algorithm #linear #polynomial #programming
Polynomial Algorithms for Linear Programming over the Algebraic Numbers (IA, PAB), pp. 483–494.
STOCSTOC-1992-BarringtonBR #representation
Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) (DAMB, RB, SR), pp. 455–461.
STOCSTOC-1992-GathenS
Computing Frobenius Maps and Factoring Polynomials (Extended Abstract) (JvzG, VS), pp. 97–105.
STOCSTOC-1992-NisanS #on the
On the Degree of Boolean Functions as Real Polynomials (NN, MS), pp. 462–467.
STOCSTOC-1992-Paturi #approximate #on the #symmetry
On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version) (RP), pp. 468–474.
ICALPICALP-1992-DietzfelbingerGMP #polynomial #reliability
Polynomial Hash Functions Are Reliable (Extended Abstract) (MD, JYG, YM, NP), pp. 235–246.
ICALPICALP-1992-KarhumakiPR #context-free grammar #polynomial #testing
Polynomial Size Test Sets for Context-Free Languages (JK, WP, WR), pp. 53–64.
ICALPICALP-1992-Mansour #approximate #random
Randomized Interpolation and Approximation of Sparse Polynomials (YM), pp. 261–272.
CADECADE-1992-CichonL #algorithm #complexity #polynomial
Polynomial Interpretations and the Complexity of Algorithms (AC, PL), pp. 139–147.
CSLCSL-1992-Stewart #bound #logic #polynomial #query
Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machines (IAS), pp. 410–424.
PODSPODS-1991-AfratiCY #datalog #on the #polynomial
On Datalog vs. Polynomial Time (FNA, SSC, MY), pp. 13–25.
STOCSTOC-1991-AspnesBFR #power of
The Expressive Power of Voting Polynomials (JA, RB, MLF, SR), pp. 402–409.
STOCSTOC-1991-BarnesR #algorithm #polynomial #sublinear #using
Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract) (GB, WLR), pp. 43–53.
STOCSTOC-1991-GemmellLRSW #approximate #self
Self-Testing/Correcting for Polynomials and for Approximate Functions (PG, RJL, RR, MS, AW), pp. 32–42.
ICALPICALP-1991-BiniGP #matrix #parallel
Improved Parallel Computations with Matrices and Polynomials (DB, LG, VYP), pp. 520–531.
ICMLML-1991-SuttonM #learning #polynomial
Learning Polynomial Functions by Feature Construction (RSS, CJM), pp. 208–212.
PODSPODS-1990-Chomicki #database #deduction #polynomial #query
Polynomial Time Query Processing in Temporal Deductive Databases (JC), pp. 379–391.
PODSPODS-1990-Saraiya #database #deduction #polynomial #program transformation
Polynomial-Time Program Transformations in Deductive Databases (YPS), pp. 132–144.
SIGMODSIGMOD-1990-Wang #design #performance #polynomial #towards
Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation (KW), pp. 74–83.
STOCSTOC-1990-BorodinT #decidability #on the #polynomial
On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version) (AB, PT), pp. 535–545.
STOCSTOC-1990-OgiwaraW #bound #on the #polynomial #set
On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (MO, OW), pp. 457–467.
ICALPICALP-1990-JerrumS #algorithm #approximate #polynomial
Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract) (MJ, AS), pp. 462–475.
ICGTGG-1990-Lichtblau #polynomial
Recognizing Rooted Context-free Flowgraph Languages in Polynomial Time (UL), pp. 538–548.
PODSPODS-1989-Saraiya #polynomial #recursion
Linearizing Nonlinear Recursions in Polynomial Time (YPS), pp. 182–189.
STOCSTOC-1989-CohenM #algorithm #detection #graph #polynomial
Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version) (EC, NM), pp. 523–534.
STOCSTOC-1989-DyerFK #algorithm #approximate #polynomial #random
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies (MED, AMF, RK), pp. 375–381.
STOCSTOC-1989-FellowsL #algorithm #on the #performance #polynomial
On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract) (MRF, MAL), pp. 501–512.
STOCSTOC-1989-PittW #approximate #automaton #consistency #polynomial #problem
The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial (LP, MKW), pp. 421–432.
SIGIRSIGIR-1989-Fuhr #polynomial #retrieval
Optimum Polynomial Retrieval Functions (NF), pp. 69–76.
CSLCSL-1989-Ambos-SpiesY #polynomial #recursion #set
Honest Polynomial-Time Degrees of Elementary Recursive Sets (KAS, DY), pp. 1–15.
LICSLICS-1989-NerodeRS #logic
Polynomially Grade Logic I: A Graded Version of System T (AN, JBR, AS), pp. 375–385.
SIGMODSIGMOD-1988-LeuchnerMS #algorithm #dependence #functional #polynomial #testing
A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies (JHL, LM, GS), pp. 218–224.
STOCSTOC-1988-Istrail #polynomial #sequence #traversal
Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract) (SI), pp. 491–503.
STOCSTOC-1988-KosarajuS #detection #graph #polynomial
Detecting Cycles in Dynamic Graphs in Polynomial Time (Preliminary Version) (SRK, GFS), pp. 398–406.
ICALPICALP-1988-LingasS #algorithm #graph #morphism #polynomial
A Polynomial-Time Algorithm for Subgraph Isomorphism of Two-Connected Series-Parallel Graphs (AL, MMS), pp. 394–409.
ICALPICALP-1988-TangB #polynomial #reduction #set
Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets (ST, RVB), pp. 591–599.
CADECADE-1988-GallierNPRS #canonical #equation #finite #polynomial #set #term rewriting
Finding Canonical Rewriting Systems Equivalent to a Finite Set of Ground Equations in Polynomial Time (JHG, PN, DAP, SR, WS), pp. 182–196.
CSLCSL-1988-Dahlhaus #nondeterminism #polynomial
Completeness with Respect to Interpretations in Deterministic and Nondeterministic Polynomial Time (ED), pp. 52–62.
CSLCSL-1988-VoigtW
A Remark on Minimal Polynomials of Boolean Functions (BV, IW), pp. 372–383.
STOCSTOC-1987-AdlemanH #polynomial #random
Recognizing Primes in Random Polynomial Time (LMA, MDAH), pp. 462–469.
STOCSTOC-1987-Kaltofen #complexity
Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials (EK), pp. 443–452.
CSLCSL-1987-Ambos-SpiesFH #polynomial
Diagonalizing over Deterministic Polynomial Time (KAS, HF, HH), pp. 1–16.
CSLCSL-1987-Spreen #nondeterminism #on the #polynomial
On Functions Computable in Nondeterministic Polynomial Time: Some Characterizations (DS), pp. 289–303.
STOCSTOC-1986-AdlemanL #finite
Finding Irreducible Polynomials over Finite Fields (LMA, HWLJ), pp. 350–355.
STOCSTOC-1986-Barrington #bound #branch #source code
Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹ (DAMB), pp. 1–5.
STOCSTOC-1986-Ben-OrFKT #algorithm #parallel #performance #polynomial
A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots (MBO, EF, DK, PT), pp. 340–349.
STOCSTOC-1986-Cai #polynomial #probability #random
With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy (JyC), pp. 21–29.
STOCSTOC-1986-KoLD #morphism #polynomial
A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract) (KIK, TJL, DZD), pp. 295–303.
ICALPICALP-1986-AverbuchWG #algorithm #classification #polynomial
Classification of all the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial (AA, SW, ZG), pp. 31–39.
CADECADE-1986-CherifaL #implementation #polynomial #term rewriting #termination
An Actual Implementation of a Procedure That Mechanically Proves Termination of Rewriting Systems Based on Inequalities Between Polynomial Interpretations (ABC, PL), pp. 42–51.
STOCSTOC-1985-Buss #bound #polynomial
The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract) (SRB), pp. 285–290.
STOCSTOC-1985-FichT #complexity #finite #parallel
The Parallel Complexity of Exponentiating Polynomials over Finite Fields (FEF, MT), pp. 38–47.
STOCSTOC-1985-FriedlR #algebra #polynomial #problem
Polynomial Time Solutions of Some Problems in Computational Algebra (KF, LR), pp. 153–162.
STOCSTOC-1985-Kaltofen #source code
Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors (EK), pp. 131–142.
ICALPICALP-1985-OrponenRS #complexity #polynomial
Polynomial Levelability and Maximal Complexity Cores (PO, DAR, US), pp. 435–444.
STOCSTOC-1984-Gonnet #equivalence #polynomial #random
Determining Equivalence of Expressions in Random Polynomial Time (Extended Abstract) (GHG), pp. 334–341.
STOCSTOC-1984-Huang #algebra #finite
Factorization of Polynomials over Finite Fields and Factorization of Primes in Algebraic Number Fields (MDAH), pp. 175–182.
STOCSTOC-1984-KannanLL #algebra #polynomial
Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers (RK, AKL, LL), pp. 191–200.
STOCSTOC-1984-Karmarkar #algorithm #linear #polynomial #programming
A New Polynomial-Time Algorithm for Linear Programming (NK), pp. 302–311.
ICALPICALP-1984-Schonhage #algorithm #integer #reduction
Factorization of Univariate Integer Polynomials by Diophantine Aproximation and an Improved Basis Reduction Algorithm (AS), pp. 436–447.
STOCSTOC-1983-Heide #algorithm #linear #polynomial #problem
A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem (FMadH), pp. 70–79.
STOCSTOC-1983-KanellakisCV #dependence #polynomial #problem
Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract) (PCK, SSC, MYV), pp. 264–277.
STOCSTOC-1983-LandauM #polynomial
Solvability by Radicals is in Polynomial Time (SL, GLM), pp. 140–151.
STOCSTOC-1983-Lenstra #finite #multi
Factoring Multivariate Polynomials over Finite Fields (Extended Abstract) (AKL), pp. 189–192.
STOCSTOC-1983-Young #polynomial #set
Some Structural Properties of Polynomial Reducibilities and Sets in NP (PY), pp. 392–401.
ICALPICALP-1983-GathenK #finite #multi #polynomial
Polynomial-Time Factorization of Multivariate Polynomials over Finite Fields (JvzG, EK), pp. 250–263.
ICALPICALP-1983-Lenstra #multi
Factoring Multivariate Integral Polynomials (AKL), pp. 458–465.
STOCSTOC-1982-DolevS #algorithm #multi #polynomial
Polynomial Algorithms for Multiple Processor Agreement (DD, HRS), pp. 401–407.
STOCSTOC-1982-Immerman #polynomial #query #relational
Relational Queries Computable in Polynomial Time (Extended Abstract) (NI), pp. 147–152.
STOCSTOC-1982-Kaltofen #multi #polynomial #reduction
A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization (EK), pp. 261–266.
ICALPICALP-1982-FlajoletS #branch #polynomial #process
A Branching Process Arising in Dynamic Hashing, Trie Searching and Polynomial Factorization (PF, JMS), pp. 239–251.
ICGTGG-1982-Schnitzler #graph #morphism #problem
The isomorphism problem is polynomially solvable for certain graph languages (MS), pp. 369–379.
STOCSTOC-1981-BertoniMS #polynomial #random
A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines (AB, GM, NS), pp. 168–176.
STOCSTOC-1981-JosephY #modelling #performance #polynomial #source code
Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract) (DJ, PY), pp. 55–61.
ICALPICALP-1981-HeintzS #decidability #polynomial #random
Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables (JH, MS), pp. 16–28.
STOCSTOC-1980-FilottiM #algorithm #graph #morphism #polynomial
A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper) (ISF, JNM), pp. 236–243.
STOCSTOC-1980-HeintzS #testing
Testing Polynomials which Are Easy to Compute (Extended Abstract) (JH, CPS), pp. 262–272.
STOCSTOC-1980-Tompa80a #algorithm #implementation #polynomial #sublinear #transitive
Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations (MT), pp. 333–338.
STOCSTOC-1979-Cook #polynomial
Deterministic CFL’s Are Accepted Simultaneously in Polynomial Time and Log Squared Space (SAC), pp. 338–345.
STOCSTOC-1979-GilbertLT #polynomial #problem
The Pebbling Problem is Complete in Polynomial Space (JRG, TL, RET), pp. 237–248.
STOCSTOC-1979-Long #on the #polynomial
On γ-Reducibility versus Polynomial Time Many-One Reducibility (Extended Abstract) (TJL), pp. 278–287.
ICALPICALP-1979-Selman #behaviour #polynomial #set
P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP (ALS), pp. 546–555.
POPLPOPL-1979-LiuF #pattern matching #polynomial #string
String Pattern Matching in Polynomial Time (KCL, ACF), pp. 222–225.
STOCSTOC-1978-Hyafil #evaluation #on the #parallel
On the Parallel Evaluation of Multivariate Polynomials (LH), pp. 193–195.
STOCSTOC-1978-Pan #complexity
Computational Complexity of Computing Polynomials over the Fields of Real and Complex Numbers (VYP), pp. 162–172.
STOCSTOC-1977-SimonG #polynomial
Polynomial Reducibilities and Upward Diagonalizations (IS, JG), pp. 186–194.
ICALPICALP-1977-PazM #approximate #nondeterminism #optimisation #polynomial #problem
Non-Deterministic Polynomial Optimization Problems and Their Approximation (AP, SM), pp. 370–379.
STOCSTOC-1976-LiptonS #evaluation
Evaluation of Polynomials with Super-Preconditioning (RJL, LJS), pp. 174–180.
STOCSTOC-1976-MandersA #polynomial #problem
NP-Complete Decision Problems for Quadratic Polynomials (KLM, LMA), pp. 23–29.
ICALPICALP-1976-Restivo #on the #product line
On a Family of Codes Related to Factorization of Cyclotomic Polynomials (AR), pp. 38–44.
STOCSTOC-1975-EvenT #combinator #polynomial #problem
a Combinatorial Problem which is Complete in Polynomial Space (SE, RET), pp. 66–71.
STOCSTOC-1975-LiptonD #complexity #evaluation #integer #metric
Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms (RJL, DPD), pp. 1–5.
STOCSTOC-1975-Wotschke #polynomial #problem #recognition
Degree-Languages, Polynomial Time Recognition, and the LBA Problem (DW), pp. 145–152.
STOCSTOC-1974-BorodinC #on the
On the Number of Additions to Compute Specific Polynomials (Preliminary Version) (AB, SAC), pp. 342–347.
STOCSTOC-1974-CookS #polynomial #requirements
Storage Requirements for Deterministic Polynomial Time Recognizable Languages (SAC, RS), pp. 33–39.
STOCSTOC-1974-JonesL #polynomial #problem
Complete Problems for Deterministic Polynomial Time (NDJ, WTL), pp. 40–46.
STOCSTOC-1974-LadnerLS #polynomial
Comparisons of Polynomial-Time Reducibilities (REL, NAL, ALS), pp. 110–121.
STOCSTOC-1974-Mehlhorn #polynomial #recursion
Polynomial and Abstract Subrecursive Classes (KM), pp. 96–109.
STOCSTOC-1973-GentlemanJ #algorithm #analysis #case study
Analysis of Algorithms, a Case Study: Determinants of Polynomials (WMG, SCJ), pp. 135–141.
STOCSTOC-1973-Greibach #context-free grammar #polynomial
Jump PDA’s, Deterministic Context-Free Languages Principal AFDLs and Polynomial Time Recognition-Extended Abstract (SAG), pp. 20–28.
STOCSTOC-1973-Ladner #polynomial
Polynomial Time Reducibility (REL), pp. 122–129.
SOSPSOSP-1973-Ullman #polynomial #problem #scheduling
Polynomial Complete Scheduling Problems (JDU), pp. 96–101.
STOCSTOC-1972-Fiduccia #algorithm #evaluation #fourier #performance #polynomial #revisited
Polynomial Evaluation via the Division Algorithm: The Fast Fourier Transform Revisited (CMF), pp. 88–93.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.