Stem polynomi$ (all stems)

444 papers:

VLDB-2015-BidoitHT #named

EFQ: Why-Not Answer Polynomials in Action (NB, MH, KT), pp. 1980–1991.

SAS-2015-AdjeGM #generative #invariant #optimisation #polynomial #using

Property-based Polynomial Invariant Generation Using Sums-of-Squares Optimization (AA, PLG, VM), pp. 235–251.

STOC-2015-AbrahamD #complexity #polynomial

Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity (IA, DD), pp. 605–614.

STOC-2015-DinurHK #composition #fault #query

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition (ID, PH, GK), pp. 267–276.

STOC-2015-DvirG #communication

2-Server PIR with Sub-Polynomial Communication (ZD, SG), pp. 577–584.

STOC-2015-FoxKM #approximate #polynomial

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection (KF, PNK, SM), pp. 841–850.

ICALP-v1-2015-FominKLPS #algorithm #polynomial

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree (FVF, PK, DL, FP, SS), pp. 494–505.

ICALP-v1-2015-Ganguly #polynomial

Taylor Polynomial Estimator for Estimating Frequency Moments (SG), pp. 542–553.

ICALP-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.

ICALP-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.

ICALP-v2-2015-JurdzinskiLS #energy #game studies #pseudo

Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time (MJ, RL, SS), pp. 260–272.

LATA-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.

CAV-2015-ChenHWZ #generative #invariant #polynomial

Counterexample-Guided Polynomial Loop Invariant Generation by Lagrange Interpolation (YFC, CDH, BYW, LZ), pp. 658–674.

CSL-2015-GasconST #polynomial #strict #unification

Two-Restricted One Context Unification is in Polynomial Time (AG, MSS, AT), pp. 405–422.

LICS-2015-GasconTS #polynomial #problem #unification

One Context Unification Problems Solvable in Polynomial Time (AG, AT, MSS), pp. 499–510.

LICS-2015-GradelPSK #first-order #polynomial

Characterising Choiceless Polynomial Time with First-Order Interpretations (EG, WP, SS, LK), pp. 677–688.

TLCA-2015-Redmond #parametricity #polynomial #λ-calculus

Polynomial Time in the Parametric λ Calculus (BFR), pp. 288–301.

ASE-2014-ZhangCHXXZM #polynomial #search-based

Search-based inference of polynomial metamorphic relations (JZ, JC, DH, YX, BX, LZ, HM), pp. 701–712.

DAC-2014-WangOC #optimisation #performance #polynomial #synthesis

Enabling Efficient Analog Synthesis by Coupling Sparse Regression and Polynomial Optimization (YW, MO, CC), p. 6.

SAS-2014-GhorbalSP #algebra #difference #equation #polynomial

Invariance of Conjunctions of Polynomial Equalities for Algebraic Differential Equations (KG, AS, AP), pp. 151–167.

STOC-2014-ChanDSS #approximate #estimation #performance #polynomial

Efficient density estimation via piecewise polynomial approximation (SoC, ID, RAS, XS), pp. 604–613.

STOC-2014-ChekuriC #bound #polynomial #theorem

Polynomial bounds for the grid-minor theorem (CC, JC), pp. 60–69.

STOC-2014-DeS #approximate #performance #polynomial

Efficient deterministic approximate counting for low-degree polynomial threshold functions (AD, RAS), pp. 832–841.

STOC-2014-KayalLSS #bound

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas (NK, NL, CS, SS), pp. 119–127.

STOC-2014-KayalSS #bound

A super-polynomial lower bound for regular arithmetic formulas (NK, CS, RS), pp. 146–153.

STOC-2014-Vegh #algorithm #polynomial

A strongly polynomial algorithm for generalized flow maximization (LAV), pp. 644–653.

ICALP-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.

ICALP-v1-2014-BjorklundH #polynomial

Shortest Two Disjoint Paths in Polynomial Time (AB, TH), pp. 211–222.

ICALP-v1-2014-DvirOS #equivalence #testing

Testing Equivalence of Polynomials under Shifts (ZD, RMdO, AS), pp. 417–428.

ICALP-v1-2014-KoppartyKS #finite #performance

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields (SK, MK, MES), pp. 726–737.

ICML-c2-2014-AndoniPV0 #learning #network

Learning Polynomials with Neural Networks (AA, RP, GV, LZ), pp. 1908–1916.

KR-2014-GottlobMP #polynomial

Polynomial Combined Rewritings for Existential Rules (GG, MM, AP).

LOPSTR-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.

RTA-TLCA-2014-CarvalhoS #decidability #polynomial #set

An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting (DdC, JGS), pp. 179–193.

SAT-2014-LarrazORR #constraints #polynomial

Minimal-Model-Guided Approaches to Solving Polynomial Constraints and Extensions (DL, AO, ERC, AR), pp. 333–350.

SMT-2014-KhanhTO #difference #named #polynomial #smt

raSAT: SMT for Polynomial Inequality (TVK, VXT, MO), p. 67.

VMCAI-2014-LeikeT #polynomial #source code #synthesis

Synthesis for Polynomial Lasso Programs (JL, AT), pp. 434–452.

CASE-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.

STOC-2013-AgrawalSS

Quasi-polynomial hitting-set for set-depth-Δ formulas (MA, CS, NS), pp. 321–330.

STOC-2013-BeckNT #calculus #polynomial #trade-off

Some trade-off results for polynomial calculus: extended abstract (CB, JN, BT), pp. 813–822.

STOC-2013-CadekKMVW

Extending continuous maps: polynomiality and undecidability (MC, MK, JM, LV, UW), pp. 595–604.

STOC-2013-KaneM

A PRG for lipschitz functions of polynomials with applications to sparsest cut (DMK, RM), pp. 1–10.

STOC-2013-KeevashKM #polynomial

Polynomial-time perfect matchings in dense hypergraphs (PK, FK, RM), pp. 311–320.

STOC-2013-KingS #polynomial

Byzantine agreement in polynomial expected time: [extended abstract] (VK, JS), pp. 401–410.

DLT-2013-FeliceN #algorithm #automaton

Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata (SDF, CN), pp. 179–190.

DLT-2013-Pin #regular expression

An Explicit Formula for the Intersection of Two Polynomials of Regular Languages (JÉP), pp. 31–45.

ICALP-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.

ICALP-v1-2013-BulanekKS #on the #online #random

On Randomized Online Labeling with Polynomially Many Labels (JB, MK, MES), pp. 291–302.

ICALP-v1-2013-DuanM #algorithm #combinator #linear #polynomial

A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market (RD, KM), pp. 425–436.

ICALP-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.

ICALP-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.

ICALP-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.

ICALP-v1-2013-JansenK #migration #online #polynomial #robust

A Robust AFPTAS for Online Bin Packing with Polynomial Migration, (KJ, KMK), pp. 589–600.

ICALP-v1-2013-LeviR #graph

A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor (RL, DR), pp. 709–720.

ICALP-v2-2013-ChristodoulouG #game studies #polynomial

Price of Stability in Polynomial Congestion Games (GC, MG), pp. 496–507.

ICALP-v2-2013-DieudonneP #approach #polynomial

Deterministic Polynomial Approach in the Plane (YD, AP), pp. 533–544.

ICALP-v2-2013-Woods #generative

Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials (KW), pp. 410–421.

LATA-2013-Blanchet-SadriBFH #approach #graph #polynomial

A Graph Polynomial Approach to Primitivity (FBS, MB, NF, JH), pp. 153–164.

KDD-2013-PhamP #kernel #performance #polynomial #scalability

Fast and scalable polynomial kernels via explicit feature maps (NP, RP), pp. 239–247.

PPDP-2013-YamadaKS #order #polynomial #recursion

Unifying the Knuth-Bendix, recursive path and polynomial orders (AY, KK, TS), pp. 181–192.

SAC-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.

CC-2013-Krause #polynomial

Optimal Register Allocation in Polynomial Time (PKK), pp. 1–20.

CGO-2013-DioufCR #heuristic #polynomial

A polynomial spilling heuristic: Layered allocation (BD, AC, FR), p. 10.

CADE-2013-KovasznaiFB #quantifier

: A Tool for Polynomially Translating Quantifier-Free Bit-Vector Formulas into (GK, AF, AB), pp. 443–449.

CAV-2013-ChengRS #constraints #named #polynomial

JBernstein: A Validity Checker for Generalized Polynomial Constraints (CHC, HR, NS), pp. 656–661.

CAV-2013-PuggelliLSS #nondeterminism #polynomial #verification

Polynomial-Time Verification of PCTL Properties of MDPs with Convex Uncertainties (AP, WL, ALSV, SAS), pp. 527–542.

CAV-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.

CASE-2012-ChenK #polynomial #probability

Polynomial test for Stochastic Diagnosability of discrete event systems (JC, RK), pp. 521–526.

PEPM-2012-MatsudaIN #cumulative #multi #polynomial #traversal

Polynomial-time inverse computation for accumulative functions with multiple data traversals (KM, KI, KN), pp. 5–14.

SAS-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.

STOC-2012-BartalGK #approximate #polynomial #problem

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme (YB, LAG, RK), pp. 663–672.

STOC-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.

STOC-2012-Kayal

Affine projections of polynomials: extended abstract (NK), pp. 643–662.

STOC-2012-Sherstov12a #robust

Making polynomials robust to noise (AAS), pp. 747–758.

STOC-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.

ICALP-v1-2012-BabaiCQ #morphism #polynomial

Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups — (Extended Abstract) (LB, PC, YQ), pp. 51–62.

ICALP-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.

ICALP-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.

ICALP-v1-2012-PolacekS #strict

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation (LP, OS), pp. 726–737.

ICALP-v2-2012-Fiore #polynomial

Discrete Generalised Polynomial Functors — (Extended Abstract) (MPF), pp. 214–226.

LATA-2012-GeilkeZ #algorithm #learning #pattern matching #polynomial

Polynomial-Time Algorithms for Learning Typed Pattern Languages (MG, SZ), pp. 277–288.

ICPR-2012-AskKA #equation #performance #polynomial #symmetry

Exploiting p-fold symmetries for faster polynomial equation solving (EA, YK, KÅ), pp. 3232–3235.

PPDP-2012-Madet #multi #polynomial #thread #λ-calculus

A polynomial time λ-calculus with multithreading and side effects (AM), pp. 55–66.

POPL-2012-SmaragdakisESYF #concurrent #detection #polynomial #predict

Sound predictive race detection in polynomial time (YS, JE, CS, JY, CF), pp. 387–400.

ICSE-2012-NguyenKWF #array #dynamic analysis #invariant #polynomial #using

Using dynamic analysis to discover polynomial and array invariants (TN, DK, WW, SF), pp. 683–693.

ICSE-2012-ZhouXZ #bound #named #polynomial #search-based

Stride: Search-based deterministic replay in polynomial time via bounded linkage (JZ, XX, CZ), pp. 892–902.

RTA-2012-FuhsK #higher-order #polynomial

Polynomial Interpretations for Higher-Order Rewriting (CF, CK), pp. 176–192.

SAT-2012-KatsirelosS #learning #satisfiability

Learning Polynomials over GF(2) in a SAT Solver — (Poster Presentation) (GK, LS), pp. 496–497.

DAC-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.

ESOP-2011-HuntS #exponential #polynomial #security #type system

From Exponential to Polynomial-Time Security Typing via Principal Types (SH, DS), pp. 297–316.

STOC-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.

DLT-J-2010-RigoW11 #finite #logic #set

Logical Characterization of Recognizable Sets of polynomials over a Finite Field (MR, LW), pp. 1549–1563.

AFL-2011-PramodK #polynomial #towards #word

Towards Shortest Synchronizing Words in Polynomial Time (VTKP, KVK), pp. 358–367.

ICALP-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.

ICALP-v1-2011-JansenS #constant #polynomial

Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth (MJJ, RS), pp. 724–735.

ICALP-v1-2011-MakarychevS #constraints

Maximizing Polynomials Subject to Assignment Constraints (KM, MS), pp. 510–520.

FM-2011-DiosP #bound #certification #memory management #polynomial

Certification of Safe Polynomial Memory Bounds (JdD, RP), pp. 184–199.

HCI-DDA-2011-ZhuYZ #polynomial

A Cubic Polynomial Model for Fisheye Camera (HZ, XY, JZ), pp. 684–693.

VLDB-2010-FanLMTWW #graph #pattern matching #polynomial

Graph Pattern Matching: From Intractable to Polynomial Time (WF, JL, SM, NT, YW, YW), pp. 264–275.

ESOP-2010-HoffmannH #analysis #polynomial

Amortized Resource Analysis with Polynomial Potential (JH, MH), pp. 287–306.

STOC-2010-Aaronson #polynomial

BQP and the polynomial hierarchy (SA), pp. 141–150.

STOC-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.

STOC-2010-DellM #polynomial #satisfiability

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (HD, DvM), pp. 251–260.

STOC-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.

STOC-2010-HaramatyS #on the #polynomial

On the structure of cubic and quartic polynomials (EH, AS), pp. 331–340.

STOC-2010-MekaZ #generative #polynomial #pseudo

Pseudorandom generators for polynomial threshold functions (RM, DZ), pp. 427–436.

STOC-2010-Patrascu #bound #polynomial #problem #towards

Towards polynomial lower bounds for dynamic problems (MP), pp. 603–610.

STOC-2010-Sherstov #bound

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials (AAS), pp. 523–532.

DLT-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.

CIAA-2010-ReidenbachS #polynomial #regular expression #scalability

A Polynomial Time Match Test for Large Classes of Extended Regular Expressions (DR, MLS), pp. 241–250.

ICALP-v1-2010-DellHW #complexity #exponential #polynomial

Exponential Time Complexity of the Permanent and the Tutte Polynomial (HD, TH, MW), pp. 426–437.

ICALP-v1-2010-Ito #approximate #proving

Polynomial-Space Approximation of No-Signaling Provers (TI), pp. 140–151.

ICALP-v1-2010-ShpilkaV #on the #polynomial #testing

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors (AS, IV), pp. 408–419.

ICALP-v2-2010-Blum #lr #on the #polynomial

On LR(k)-Parsers of Polynomial Size (NB), pp. 163–174.

ICPR-2010-PernekH #polynomial #problem #re-engineering

Perspective Reconstruction and Camera Auto-Calibration as Rectangular Polynomial Eigenvalue Problem (ÁP, LH), pp. 49–52.

SAC-2010-FunfzigMF #polynomial

Polytope-based computation of polynomial ranges (CF, DM, SF), pp. 1247–1252.

IJCAR-2010-NeurauterMZ #polynomial

Monotonicity Criteria for Polynomial Interpretations over the Naturals (FN, AM, HZ), pp. 502–517.

LICS-2010-Grohe #fixpoint #graph #polynomial

Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors (MG), pp. 179–188.

LICS-2010-Laubner #graph #polynomial

Capturing Polynomial Time on Interval Graphs (BL), pp. 199–208.

RTA-2010-NeurauterM #integer #polynomial

Polynomial Interpretations over the Reals do not Subsume Polynomial Interpretations over the Integers (FN, AM), pp. 243–258.

RTA-2010-Waldmann #bound #matrix

Polynomially Bounded Matrix Interpretations (JW), pp. 357–372.

DAC-2009-HuLA #approximate #polynomial

A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion (SH, ZL, CJA), pp. 424–429.

DAC-2009-SarbisheiAF #clustering #heuristic #optimisation #polynomial #using

Polynomial datapath optimization using partitioning and compensation heuristics (OS, BA, MF), pp. 931–936.

DATE-2009-GopalakrishnanK #algebra #polynomial #synthesis

Algebraic techniques to enhance common sub-expression elimination for polynomial system synthesis (SG, PK), pp. 1452–1457.

DATE-2009-WangCTHR #modelling #optimisation #performance #polynomial #using

An efficient decoupling capacitance optimization using piecewise polynomial models (XW, YC, SXDT, XH, JR), pp. 1190–1195.

PODS-2009-Parys #complexity #evaluation #linear #polynomial #xpath

XPath evaluation in linear time with polynomial combined complexity (PP), pp. 55–64.

FoSSaCS-2009-BonsangueRS #algebra #polynomial #theorem

A Kleene Theorem for Polynomial Coalgebras (MMB, JJMMR, AS), pp. 122–136.

STOC-2009-BabaiBS #matrix #polynomial

Polynomial-time theory of matrix groups (LB, RB, ÁS), pp. 55–64.

STOC-2009-Ben-SassonK

Affine dispersers from subspace polynomials (EBS, SK), pp. 65–74.

ICALP-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.

ICALP-v2-2009-BrancoP #equation #polynomial #regular expression

Equations Defining the Polynomial Closure of a Lattice of Regular Languages (MJJB, JÉP), pp. 115–126.

FM-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.

ICML-2009-KolterN #polynomial

Near-Bayesian exploration in polynomial time (JZK, AYN), pp. 513–520.

ICML-2009-SzitaL #learning #polynomial

Optimistic initialization and greediness lead to polynomial time learning in factored MDPs (IS, AL), pp. 1001–1008.

CADE-2009-BorrallerasLNRR #linear #polynomial #satisfiability

Solving Non-linear Polynomial Arithmetic via SAT Modulo Linear Arithmetic (CB, SL, RNM, ERC, AR), pp. 294–305.

CAV-2009-DangS #image #polynomial #using

Image Computation for Polynomial Dynamical Systems Using the Bernstein Expansion (TD, DS), pp. 219–232.

CSL-2009-Grohe #fixpoint #polynomial

Fixed-Point Definability and Polynomial Time (MG), pp. 20–23.

LICS-2009-BonsangueRS #algebra #polynomial

An Algebra for Kripke Polynomial Coalgebras (MMB, JJMMR, AS), pp. 49–58.

RTA-2009-AvanziniM #dependence #order #polynomial

Dependency Pairs and Polynomial Path Orders (MA, GM), pp. 48–62.

CASE-2008-ChuCSC #algorithm #polynomial

An O(T3) Polynomial algorithm for crude oil transportation (FC, CC, QS, HC), pp. 303–308.

DAC-2008-QianR #logic #polynomial #probability #robust #synthesis

The synthesis of robust polynomial arithmetic with stochastic logic (WQ, MDR), pp. 648–653.

DATE-2008-MasrurDF #polynomial #testing

Improvements in Polynomial-Time Feasibility Testing for EDF (AM, SD, GF), pp. 1033–1038.

SAS-2008-SeidlFP #equation #polynomial

Analysing All Polynomial Equations in ℤ₂ᵂ (HS, AF, MP), pp. 299–314.

STOC-2008-Lovett #generative #pseudo

Unconditional pseudorandom generators for low degree polynomials (SL), pp. 557–562.

STOC-2008-ShpilkaV #polynomial #testing

Read-once polynomial identity testing (AS, IV), pp. 507–516.

STOC-2008-Umans #composition #performance #polynomial

Fast polynomial factorization and modular composition in small characteristic (CU), pp. 481–490.

DLT-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.

ICALP-A-2008-BlaserHS #set

Asymptotically Optimal Hitting Sets Against Polynomials (MB, MH, DS), pp. 345–356.

ICALP-A-2008-BodlaenderDFH #kernel #on the #polynomial #problem

On Problems without Polynomial Kernels (Extended Abstract) (HLB, RGD, MRF, DH), pp. 563–574.

ICALP-A-2008-DiakonikolasLMSW #testing

Efficiently Testing Sparse GF(2) Polynomials (ID, HKL, KM, RAS, AW), pp. 502–514.

ICALP-A-2008-EsparzaGKS #approximate #equation

Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations (JE, TG, SK, HS), pp. 698–710.

ICALP-A-2008-FrandsenS #normalisation #polynomial

Dynamic Normal Forms and Dynamic Characteristic Polynomial (GSF, PS), pp. 434–446.

ICALP-A-2008-IwamaNPRY #linear #network #polynomial

Polynomial-Time Construction of Linear Network Coding (KI, HN, MP, RR, SY), pp. 271–282.

ICALP-B-2008-Chen #constraints #quantifier

Quantified Constraint Satisfaction and the Polynomially Generated Powers Property (HC), pp. 197–208.

SOFTVIS-2008-ThompsonPAH #polynomial #visualisation

Visualizing the computation tree of the Tutte Polynomial (BT, DJP, CA, GH), pp. 211–212.

ICPR-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.

PPDP-2008-MarionP #complexity #polynomial

Characterizations of polynomial complexity classes with a better intensionality (JYM, RP), pp. 79–88.

LICS-2008-Riis #calculus #complexity #on the #polynomial #proving

On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity (SR), pp. 272–283.

DATE-2007-BonziniP #automation #polynomial #set

Polynomial-time subgraph enumeration for automated instruction set extension (PB, LP), pp. 1331–1336.

PODS-2007-FiliotNTT #polynomial #xpath

Polynomial time fragments of XPath with variables (EF, JN, JMT, ST), pp. 205–214.

FoSSaCS-2007-MarnetteKR #bound #constraints #polynomial #set

Polynomial Constraints for Sets with Cardinality Bounds (BM, VK, MCR), pp. 258–273.

STOC-2007-ChuzhoyK #polynomial #problem

Polynomial flow-cut gaps and hardness of directed cut problems (JC, SK), pp. 179–188.

STOC-2007-GoldbergJ #polynomial

Inapproximability of the Tutte polynomial (LAG, MJ), pp. 459–468.

STOC-2007-HavivR #polynomial #problem

Tensor-based hardness of the shortest vector problem to within almost polynomial factors (IH, OR), pp. 469–477.

STOC-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.

CIAA-J-2006-BastienCFR07 #exponential

Reducing Simple Grammars: Exponential against Highly-Polynomial Time in Practice (CB, JC, WF, WR), pp. 715–725.

ICALP-2007-BlaserD #complexity #polynomial

Complexity of the Cover Polynomial (MB, HD), pp. 801–812.

PPDP-2007-Lucas #proving #termination

Practical use of polynomials over the reals in proofs of termination (SL), pp. 39–50.

SAT-2007-Buresh-OppenheimM #polynomial

Minimum 2CNF Resolution Refutations in Polynomial Time (JBO, DGM), pp. 300–313.

SAT-2007-FuhsGMSTZ #analysis #polynomial #satisfiability #termination

SAT Solving for Termination Analysis with Polynomial Interpretations (CF, JG, AM, PSK, RT, HZ), pp. 340–354.

SAT-2007-Kullmann #invariant #matrix #polynomial #satisfiability

Polynomial Time SAT Decision for Complementation-Invariant Clause-Sets, and Sign-non-Singular Matrices (OK), pp. 314–327.

TLCA-2007-Baillot #linear #logic #polynomial #type system

From Proof-Nets to Linear Logic Type Systems for Polynomial Time Computing (PB), pp. 2–7.

TLCA-2007-ShkaravskaKE #analysis #first-order #polynomial

Polynomial Size Analysis of First-Order Functions (OS, RvK, MCJDvE), pp. 351–365.

CASE-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.

CASE-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.

PODS-2006-GottlobN #polynomial

Data exchange: computing cores in polynomial time (GG, AN), pp. 40–49.

VLDB-2006-CohenFKKS

Full Disjunctions: Polynomial-Delay Iterators in Action (SC, IF, YK, BK, YS), pp. 739–750.

STOC-2006-AharonovJL #algorithm #approximate #polynomial #quantum

A polynomial quantum algorithm for approximating the Jones polynomial (DA, VJ, ZL), pp. 427–436.

STOC-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.

STOC-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.

STOC-2006-KelnerS #algorithm #linear #polynomial #programming #random

A randomized polynomial-time simplex algorithm for linear programming (JAK, DAS), pp. 51–60.

STOC-2006-Rao #constant #independence

Extractors for a constant number of polynomially small min-entropy independent sources (AR), pp. 497–506.

STOC-2006-RemyS #approximate

A quasi-polynomial time approximation scheme for minimum weight triangulation (JR, AS), pp. 316–325.

CIAA-2006-BastienCFR #exponential

Reducing Simple Grammars: Exponential Against Highly-Polynomial Time in Practice (CB, JC, WF, WR), pp. 90–101.

DLT-2006-GlasserTW #polynomial

Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy (CG, SDT, KWW), pp. 408–419.

DLT-2006-Kufleitner #logic

Polynomials, Fragments of Temporal Logic and the Variety DA over Traces (MK), pp. 37–48.

ICALP-v2-2006-KariantoKT #on the #problem #set

On Intersection Problems for Polynomially Generated Sets (KW, AK, WT), pp. 516–527.

KDD-2006-Jaroszewicz #polynomial

Polynomial association rules with applications to logistic regression (SJ), pp. 586–591.

LOPSTR-2006-NguyenS #automation #named #polynomial #proving #termination

Polytool: Proving Termination Automatically Based on Polynomial Interpretations (MTN, DDS), pp. 210–218.

SAC-2006-BoldoM #evaluation

Provably faithful evaluation of polynomials (SB, CM), pp. 1328–1332.

SAC-2006-GraillatL #pseudo #set

Pseudozero set of interval polynomials (SG, PL), pp. 1655–1659.

CAV-2006-RoyZFH #consistency #memory management #performance #polynomial #verification

Fast and Generalized Polynomial Time Memory Consistency Verification (AR, SZ, CJF, JCH), pp. 503–516.

IJCAR-2006-BaaderLS #named #ontology #polynomial

CEL — A Polynomial-Time Reasoner for Life Science Ontologies (FB, CL, BS), pp. 287–291.

IJCAR-2006-Mahboubi #algorithm #implementation #performance #proving

Proving Formally the Implementation of an Efficient gcd Algorithm for Polynomials (AM), pp. 438–452.

DATE-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.

STOC-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.

STOC-2005-Bogdanov #generative #pseudo

Pseudorandom generators for low degree polynomials (AB), pp. 21–30.

STOC-2005-DvirS #polynomial #query #testing

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits (ZD, AS), pp. 592–601.

STOC-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.

DLT-J-2004-BorchertLSTT05 #polynomial

The dot-depth and the polynomial hierarchies correspond on the delta levels (BB, KJL, FS, PT, DT), pp. 625–644.

DLT-2005-Kortelainen #generative #polynomial #recursion

Polynomial Generators of Recursively Enumerable Languages (JK), pp. 320–326.

ICALP-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.

ICALP-2005-DiehlM #bound #polynomial #random

Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines (SD, DvM), pp. 982–993.

ICALP-2005-Kayal #equation #finite #polynomial

Solvability of a System of Bivariate Polynomial Equations over a Finite Field (NK), pp. 551–562.

ICALP-2005-Kovacs #multi #polynomial

Polynomial Time Preemptive Sum-Multicoloring on Paths (AK), pp. 840–852.

SAT-J-2004-GalesiK05 #polynomial #rank #satisfiability

Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank (NG, OK), pp. 89–104.

CSL-2005-SchurmannS #identification #polynomial #recursion

Identifying Polynomial-Time Recursive Functions (CS, JS), pp. 525–540.

ICLP-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.

LICS-2005-Leroux #diagrams #polynomial #synthesis

A Polynomial Time Presburger Criterion and Synthesis for Number Decision Diagrams (JL), pp. 147–156.

VMCAI-2005-BradleyMS #polynomial #source code #termination

Termination of Polynomial Programs (ARB, ZM, HBS), pp. 113–129.

DATE-v1-2004-RaudvereSSJ #abstraction #polynomial #verification

Polynomial Abstraction for Verification of Sequentially Implemented Combinational Circuits (TR, AKS, IS, AJ), pp. 690–691.

SIGMOD-2004-NgC

Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials (YC, RTN), pp. 599–610.

FoSSaCS-2004-BaillotM #polynomial #λ-calculus

Soft λ-Calculus: A Language for Polynomial Time Computation (PB, VM), pp. 27–41.

FoSSaCS-2004-Lucas #proving #termination

Polynomials for Proving Termination of Context-Sensitive Rewriting (SL), pp. 318–332.

TACAS-2004-SuW #analysis #constraints

A Class of Polynomially Solvable Range Constraints for Interval Analysis without Widenings and Narrowings (ZS, DW), pp. 280–295.

SAS-2004-GulwaniN #algorithm #polynomial

A Polynomial-Time Algorithm for Global Value Numbering (SG, GCN), pp. 212–227.

SAS-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.

STOC-2004-Ajtai #polynomial

A conjecture about polynomial time computable lattice-lattice functions (MA), pp. 486–493.

STOC-2004-DunaganV #algorithm #linear #polynomial #source code

A simple polynomial-time rescaling algorithm for solving linear programs (JD, SV), pp. 315–320.

STOC-2004-Raz #multi

Multi-linear formulas for permanent and determinant are of super-polynomial size (RR), pp. 633–641.

STOC-2004-SanthaS #quantum #query

Quantum and classical query complexities of local search are polynomially related (MS, MS), pp. 494–501.

DLT-2004-BorchertLSTT #polynomial

The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels (BB, KJL, FS, PT, DT), pp. 89–101.

ICALP-2004-Midrijanis #bound #polynomial #problem #quantum #query #set #similarity

A Polynomial Quantum Query Lower Bound for the Set Equality Problem (GM), pp. 996–1005.

ICML-2004-BohteBG #classification #parametricity #polynomial

Nonparametric classification with polynomial MPMC cascades (SMB, MB, GZG).

ICPR-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.

ICPR-v3-2004-LuoWH #graph

Graph Manifolds from Spectral Polynomials (BL, RCW, ERH), pp. 402–405.

KR-2004-BaralE #algorithm #policy #polynomial

A Polynomial-Time Algorithm for Constructing k-Maintainable Policies (CB, TE), pp. 720–730.

SIGIR-2004-KokiopoulouS #information retrieval #polynomial #semantics

Polynomial filtering in latent semantic indexing for information retrieval (EK, YS), pp. 104–111.

POPL-2004-Fiore #morphism #polynomial #recursion

Isomorphisms of generic recursive polynomial types (MPF), pp. 77–88.

LICS-2004-BaillotT #polynomial #λ-calculus

Light Types for Polynomial Time Computation in λ-Calculus (PB, KT), pp. 266–275.

SAT-2004-GalesiK #polynomial #rank #satisfiability

Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank (NG, OK), pp. 76–85.

DAC-2003-DongR #polynomial #reduction

Piecewise polynomial nonlinear model reduction (ND, JSR), pp. 484–489.

FoSSaCS-2003-BournezCNM #parallel #polynomial

Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time (OB, FC, PJdN, JYM), pp. 185–199.

STOC-2003-AzarCFKR #polynomial

Optimal oblivious routing in polynomial time (YA, EC, AF, HK, HR), pp. 383–388.

STOC-2003-BeierV #polynomial #random

Random knapsack in expected polynomial time (RB, BV), pp. 232–241.

STOC-2003-KabanetsI #bound #polynomial #proving #testing

Derandomizing polynomial identity tests means proving circuit lower bounds (VK, RI), pp. 355–364.

STOC-2003-ODonnellS #bound #polynomial

New degree bounds for polynomial threshold functions (RO, RAS), pp. 325–334.

FME-2003-MussetR #linear

Computing Meta-transitions for Linear Transition Systems with Polynomials (JM, MR), pp. 562–581.

CSL-2003-KanovichV #problem

Coping Polynomially with Numerous but Identical Elements within Planning Problems (MIK, JV), pp. 285–298.

ICLP-2003-Rao #polynomial

Polynomial-Time Learnability from Entailment (MRKKR), pp. 489–491.

LICS-2003-Oliva #algorithm #effectiveness #polynomial #proving

Polynomial-time Algorithms from Ineffective Proofs (PO), pp. 128–137.

DATE-2002-ChenBKR #reduction #using

Model Reduction in the Time-Domain Using Laguerre Polynomials and Krylov Methods (YC, VB, CKK, KR), pp. 931–935.

DATE-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.

PLDI-2002-DasLS #named #polynomial #verification

ESP: Path-Sensitive Program Verification in Polynomial Time (MD, SL, MS), pp. 57–68.

SAS-2002-Lee #analysis #polynomial

Finiteness Analysis in Polynomial Time (CSL), pp. 493–508.

SAS-2002-Muller-OlmS #decidability #polynomial

Polynomial Constants Are Decidable (MMO, HS), pp. 4–19.

STOC-2002-BarakL #polynomial #simulation #strict

Strict polynomial-time in simulation and extraction (BB, YL), pp. 484–493.

STOC-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.

STOC-2002-Hallgren #algorithm #equation #polynomial #problem #quantum

Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem (SH), pp. 653–658.

CIAA-2002-Trahtman #algorithm #polynomial #testing

A Polynomial Time Algorithm for Left [Right] Local Testability (ANT), pp. 203–212.

ICALP-2002-CzumajLZ #approximate #design #network #polynomial #problem

Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem (AC, AL, HZ), pp. 973–984.

ICALP-2002-ImpagliazzoS #axiom #bound #simulation

Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations (RI, NS), pp. 208–219.

ICALP-2002-IshaiK

Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials (YI, EK), pp. 244–256.

ICML-2002-FitzgibbonDA #approximate #monte carlo #polynomial

Univariate Polynomial Inference by Monte Carlo Message Length Approximation (LJF, DLD, LA), pp. 147–154.

ICPR-v2-2002-ErcilB #classification #polynomial #using

One Class Classification Using Implicit Polynomial Surface Fitting (AE, BB), pp. 152–155.

GPCE-2002-Lee #analysis #polynomial #termination

Program Termination Analysis in Polynomial Time (CSL), pp. 218–235.

ICLP-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.

LICS-2002-Tiwari #confluence #polynomial #term rewriting

Deciding Confluence of Certain Term Rewriting Systems in Polynomial Time (AT), p. 447–?.

ESOP-2001-Mitchell #analysis #calculus #polynomial #probability #process #protocol #security

Probabilistic Polynomial-Time Process Calculus and Security Protocol Analysis (JCM), pp. 23–29.

STOC-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.

STOC-2001-KlivansS #multi #performance #testing

Randomness efficient identity testing of multivariate polynomials (AK, DAS), pp. 216–223.

STOC-2001-Shparlinski #approximate #finite #polynomial

Sparse polynomial approximation in finite fields (IS), pp. 209–215.

STOC-2001-SpielmanT #algorithm #analysis #polynomial #why

Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time (DAS, SHT), pp. 296–305.

STOC-2001-Valiant #polynomial #quantum

Quantum computers that can be simulated classically in polynomial time (LGV), pp. 114–123.

ICALP-2001-KiayiasY #game studies #polynomial

Secure Games with Polynomial Expressions (AK, MY), pp. 939–950.

IFL-2001-PenaS01a #analysis #nondeterminism

A Polynomial-Cost Non-determinism Analysis (RP, CS), pp. 121–137.

STOC-2000-GurvitsS #algorithm #approximate #polynomial

A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume (LG, AS), pp. 48–57.

STOC-2000-IwataFF #algorithm #combinator #polynomial

A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions (SI, LF, SF), pp. 97–106.

STOC-2000-KenyonSY #approximate #polynomial

Polynomial-time approximation scheme for data broadcast (CK, NS, NEY), pp. 659–666.

STOC-2000-LiMW #multi #polynomial

Near optimal multiple alignment within a band in polynomial time (ML, BM, LW), pp. 425–434.

WLC-2000-MargolisS #polynomial

Power Semigroups and Polynomial Closure (SWM, BS), pp. 311–322.

WLC-2000-Nishio #automaton #finite

Cellular Automata with Polynomials over Finite Fields (HN), pp. 370–377.

ICML-2000-CampbellTB #network #polynomial #reduction

Dimension Reduction Techniques for Training Polynomial Networks (WMC, KT, SVB), pp. 119–126.

ICPR-v3-2000-HelzerBM #2d #robust

Robust Fitting of Implicit Polynomials with Quantized Coefficients to 2D Data (AH, MB, DM), pp. 3294–3297.

CSL-2000-BlassG00a #polynomial

Choiceless Polynomial Time Computation and the Zero-One Law (AB, YG), pp. 18–40.

LICS-2000-AehligS #analysis #polynomial

A Syntactical Analysis of Non-Size-Increasing Polynomial Time Computation (KA, HS), pp. 84–91.

DATE-1999-SmithM #component #polynomial

Polynomial Methods for Allocating Complex Components (JS, GDM), pp. 217–222.

FoSSaCS-1999-DantsinV #algorithm #nondeterminism #polynomial #set #unification

A Nondeterministic Polynomial-Time Unification Algorithm for Bags, Sets and Trees (ED, AV), pp. 180–196.

STOC-1999-BussGIP #calculus #linear #polynomial

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (SRB, DG, RI, TP), pp. 547–556.

STOC-1999-CaiNS #probability #theorem

Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time (JyC, AN, DS), pp. 726–735.

STOC-1999-ChenM #approximate #multi #polynomial #scheduling

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract) (JC, AM), pp. 418–427.

STOC-1999-DinurFKRS #towards

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (ID, EF, GK, RR, SS), pp. 29–40.

STOC-1999-JansenSS #approximate #polynomial

Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme (KJ, RSO, MS), pp. 394–399.

STOC-1999-KlivansM #graph #morphism #polynomial #proving

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (AK, DvM), pp. 659–667.

STOC-1999-NaorP #evaluation #polynomial

Oblivious Transfer and Polynomial Evaluation (MN, BP), pp. 245–254.

STOC-1999-Schaefer #graph #polynomial

Graph Ramsey Theory and the Polynomial Hierarchy (MS), pp. 592–601.

STOC-1999-Wayne #algorithm #combinator #polynomial

A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow (KDW), pp. 11–18.

ICALP-1999-OlshevskyP #evaluation #matrix #polynomial

Polynomial and Rational Evaluation and Interpolation (with Structured Matrices) (VO, VYP), pp. 585–594.

FM-v1-1999-LincolnMMS #analysis #equivalence #polynomial #probability #security

Probabilistic Polynomial-Time Equivalence and Security Analysis (PL, JCM, MM, AS), pp. 776–793.

ICML-1999-ParekhH #automaton

Simple DFA are Polynomially Probably Exactly Learnable from Simple Examples (RP, VH), pp. 298–306.

LICS-1999-Hofmann99a #linear #polynomial

Linear Types and Non-Size-Increasing Polynomial Time Computation (MH0), pp. 464–473.

RTA-1999-Gobel #performance #symmetry

Fast Rewriting of Symmetric Polynomials (MG), pp. 371–381.

DATE-1998-ChuW #algorithm #polynomial

A Polynomial Time Optimal Algorithm for Simultaneous Buffer and Wire Sizing (CCNC, DFW), pp. 479–485.

STOC-1998-LewinV #polynomial #question #towards

Checking Polynomial Identities over any Field: Towards a Derandomization? (DL, SPV), pp. 438–447.

STOC-1998-LinialSW #algorithm #approximate #matrix #polynomial #scalability

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents (NL, AS, AW), pp. 644–652.

STOC-1998-MourrainP #equation #multi #polynomial

Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations (BM, VYP), pp. 488–496.

STOC-1998-NatanzonSS #algorithm #approximate #polynomial #problem

A Polynomial Approximation Algorithm for the Minimum Fill-In Problem (AN, RS, RS), pp. 41–47.

ICALP-1998-CzumajL #approximate #polynomial

A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity (AC, AL), pp. 682–694.

ICALP-1998-DyerG #algorithm #polynomial

A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables (MED, CSG), pp. 339–350.

CSL-1998-BonfanteCMT #complexity #polynomial #term rewriting

Complexity Classes and Rewrite Systems with Polynomial Interpretation (GB, AC, JYM, HT), pp. 372–384.

ICDAR-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.

SAS-1997-Braunburger #analysis #automation #order #polynomial #termination #using

Automatic Termination Analysis for Partial Functions Using Polynomial Orderings (JB), pp. 330–344.

SAS-1997-Frey #polynomial #type system

Satisfying Subtype Inequalities in Polynomial Space (AF), pp. 265–277.

STOC-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.

STOC-1997-Reif #approximate #constant #evaluation #polynomial

Approximate Complex Polynomial Evaluation in Near Constant Work Per Point (JHR), pp. 30–39.

ICALP-1997-CodenottiEGK

Checking Properties of Polynomials (Extended Abstract) (BC, FE, PG, RK), pp. 203–213.

ICML-1997-MooreSD #performance #polynomial #predict

Efficient Locally Weighted Polynomial Regression Predictions (AWM, JGS, KD), pp. 236–244.

SAC-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.

RTA-1997-BachmairT #commutative #polynomial

D-Bases for Polynomial Ideals over Commutative Noetherian Rings (LB, AT), pp. 113–127.

SAS-1996-Givan #polynomial #specification

Inferring Program Specifications in Polynomial-Time (RG), pp. 205–219.

ICALP-1996-Fernandez-BacaL #algorithm #polynomial

A Polynomial-Time Algorithm for Near-Perfect Phylogeny (DFB, JL), pp. 670–680.

ICALP-1996-FlajoletGP #polynomial #random

Random Polynomials and Polynomial Factorization (PF, XG, DP), pp. 232–243.

ICPR-1996-Molina-GamezS #approach #polynomial #recognition

Sparse groups: A polynomial middle-level approach for object recognition (MCMG, JBSV), pp. 518–522.

CADE-1996-HermannK #algorithm #polynomial #unification

Unification Algorithms Cannot be Combined in Polynomial Time (MH, PGK), pp. 246–260.

CAV-1996-Baier #algorithm #bisimulation #polynomial #probability #simulation #testing

Polynomial Time Algorithms for Testing Probabilistic Bisimulation and Simulation (CB), pp. 50–61.

LICS-1996-Narendran #equation #linear #polynomial

Solving Linear Equations over Polynomial Semirings (PN), pp. 466–472.

SAS-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.

STOC-1995-AroraKK #approximate #np-hard #polynomial #problem

Polynomial time approximation schemes for dense instances of NP-hard problems (SA, DRK, MK), pp. 284–293.

STOC-1995-HannenhalliP #algorithm #permutation #polynomial #sorting

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals (SH, PAP), pp. 178–189.

STOC-1995-KaltofenS #finite

Subquadratic-time factoring of polynomials over finite fields (EK, VS), pp. 398–406.

STOC-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.

STOC-1995-KarpinskiM #bound #network #polynomial

Polynomial bounds for VC dimension of sigmoidal neural networks (MK, AM), pp. 200–208.

STOC-1995-KushilevitzOR #communication #polynomial

Log-space polynomial end-to-end communication (EK, RO, AR), pp. 559–568.

STOC-1995-Pan #algorithm #approximate #parallel #polynomial

Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros (VYP), pp. 741–750.

STOC-1995-Reif #parallel #performance #polynomial

Work efficient parallel solution of Toeplitz systems and polynomial GCD (JHR), pp. 751–761.

ICALP-1995-Ambos-Spies #approximate #on the #polynomial

On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (Extended Abstract) (KAS), pp. 384–392.

ICALP-1995-PinW #ambiguity #polynomial

Polynomial Closure and Unambiguous Product (JÉP, PW), pp. 348–359.

CAV-1995-Lescow #finite #game studies #on the #source code

On Polynomial-Size Programs Winning Finite-State Games (HL), pp. 239–252.

RTA-1995-Giesl #generative #order #polynomial #proving #termination

Generating Polynomial Orderings for Termination Proofs (JG), pp. 426–431.

RTA-1995-Senizergues #algorithm #confluence #polynomial #testing

A Polynomial Algorithm Testing Partial Confluence of Basic Semi-Thue Systems (GS), pp. 194–209.

ICALP-1994-HoftingW #analysis #graph #polynomial

Polynomial Time Analysis of Torodial Periodic Graphs (FH, EW), pp. 544–555.

ICALP-1994-Pin #polynomial #set

Polynomial Closure of Group Languages and Open Sets of the Hall Topology (JÉP), pp. 424–435.

SAC-1994-InsallMW #finite

Conjugating polynomials on finite rings (MI, LM, RWW), pp. 277–280.

DAC-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.

DAC-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.

STOC-1993-GarayM #polynomial

Fully polynomial Byzantine agreement in t+1 rounds (JAG, YM), pp. 31–41.

STOC-1993-Goldberg #algorithm #graph #polynomial #product line

Polynomial space polynomial delay algorithms for listing families of graphs (LAG), pp. 218–225.

STOC-1993-Shamir #generative #multi #on the

On the generation of multivariate polynomials which are hard to factor (AS), pp. 796–804.

ICALP-1993-Kann #approximate #bound #problem

Polynomially Bounded Minimization Problems which are Hard to Approximate (VK), pp. 52–63.

ICALP-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.

RTA-1993-Plaisted #constraints #polynomial #termination #testing

Polynomial Time Termination and Constraint Satisfaction Tests (DAP), pp. 405–420.

STOC-1992-AdlerB #algebra #algorithm #linear #polynomial #programming

Polynomial Algorithms for Linear Programming over the Algebraic Numbers (IA, PAB), pp. 483–494.

STOC-1992-BarringtonBR #representation

Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) (DAMB, RB, SR), pp. 455–461.

STOC-1992-GathenS

Computing Frobenius Maps and Factoring Polynomials (Extended Abstract) (JvzG, VS), pp. 97–105.

STOC-1992-NisanS #on the

On the Degree of Boolean Functions as Real Polynomials (NN, MS), pp. 462–467.

STOC-1992-Paturi #approximate #on the #symmetry

On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version) (RP), pp. 468–474.

ICALP-1992-DietzfelbingerGMP #polynomial #reliability

Polynomial Hash Functions Are Reliable (Extended Abstract) (MD, JYG, YM, NP), pp. 235–246.

ICALP-1992-KarhumakiPR #context-free grammar #polynomial #testing

Polynomial Size Test Sets for Context-Free Languages (JK, WP, WR), pp. 53–64.

ICALP-1992-Mansour #approximate #random

Randomized Interpolation and Approximation of Sparse Polynomials (YM), pp. 261–272.

CADE-1992-CichonL #algorithm #complexity #polynomial

Polynomial Interpretations and the Complexity of Algorithms (AC, PL), pp. 139–147.

CSL-1992-Stewart #bound #logic #polynomial #query

Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machines (IAS), pp. 410–424.

PODS-1991-AfratiCY #datalog #on the #polynomial

On Datalog vs. Polynomial Time (FNA, SSC, MY), pp. 13–25.

STOC-1991-AspnesBFR #power of

The Expressive Power of Voting Polynomials (JA, RB, MLF, SR), pp. 402–409.

STOC-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.

STOC-1991-GemmellLRSW #approximate #self

Self-Testing/Correcting for Polynomials and for Approximate Functions (PG, RJL, RR, MS, AW), pp. 32–42.

ICALP-1991-BiniGP #matrix #parallel

Improved Parallel Computations with Matrices and Polynomials (DB, LG, VYP), pp. 520–531.

ML-1991-SuttonM #learning #polynomial

Learning Polynomial Functions by Feature Construction (RSS, CJM), pp. 208–212.

PODS-1990-Chomicki #database #deduction #polynomial #query

Polynomial Time Query Processing in Temporal Deductive Databases (JC), pp. 379–391.

PODS-1990-Saraiya #database #deduction #polynomial #program transformation

Polynomial-Time Program Transformations in Deductive Databases (YPS), pp. 132–144.

SIGMOD-1990-Wang #design #performance #polynomial #towards

Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation (KW), pp. 74–83.

STOC-1990-BorodinT #decidability #on the #polynomial

On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version) (AB, PT), pp. 535–545.

STOC-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.

ICALP-1990-JerrumS #algorithm #approximate #polynomial

Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract) (MJ, AS), pp. 462–475.

GG-1990-Lichtblau #polynomial

Recognizing Rooted Context-free Flowgraph Languages in Polynomial Time (UL), pp. 538–548.

PODS-1989-Saraiya #polynomial #recursion

Linearizing Nonlinear Recursions in Polynomial Time (YPS), pp. 182–189.

STOC-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.

STOC-1989-DyerFK #algorithm #approximate #polynomial #random

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies (MED, AMF, RK), pp. 375–381.

STOC-1989-FellowsL #algorithm #on the #performance #polynomial

On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract) (MRF, MAL), pp. 501–512.

STOC-1989-PittW #approximate #automaton #consistency #polynomial #problem

The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial (LP, MKW), pp. 421–432.

SIGIR-1989-Fuhr #polynomial #retrieval

Optimum Polynomial Retrieval Functions (NF), pp. 69–76.

CSL-1989-Ambos-SpiesY #polynomial #recursion #set

Honest Polynomial-Time Degrees of Elementary Recursive Sets (KAS, DY), pp. 1–15.

LICS-1989-NerodeRS #logic

Polynomially Grade Logic I: A Graded Version of System T (AN, JBR, AS), pp. 375–385.

SIGMOD-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.

STOC-1988-Istrail #polynomial #sequence #traversal

Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract) (SI), pp. 491–503.

STOC-1988-KosarajuS #detection #graph #polynomial

Detecting Cycles in Dynamic Graphs in Polynomial Time (Preliminary Version) (SRK, GFS), pp. 398–406.

ICALP-1988-LingasS #algorithm #graph #morphism #polynomial

A Polynomial-Time Algorithm for Subgraph Isomorphism of Two-Connected Series-Parallel Graphs (AL, MMS), pp. 394–409.

ICALP-1988-TangB #polynomial #reduction #set

Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets (ST, RVB), pp. 591–599.

CADE-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.

CSL-1988-Dahlhaus #nondeterminism #polynomial

Completeness with Respect to Interpretations in Deterministic and Nondeterministic Polynomial Time (ED), pp. 52–62.

CSL-1988-VoigtW

A Remark on Minimal Polynomials of Boolean Functions (BV, IW), pp. 372–383.

STOC-1987-AdlemanH #polynomial #random

Recognizing Primes in Random Polynomial Time (LMA, MDAH), pp. 462–469.

STOC-1987-Kaltofen #complexity

Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials (EK), pp. 443–452.

CSL-1987-Ambos-SpiesFH #polynomial

Diagonalizing over Deterministic Polynomial Time (KAS, HF, HH), pp. 1–16.

CSL-1987-Spreen #nondeterminism #on the #polynomial

On Functions Computable in Nondeterministic Polynomial Time: Some Characterizations (DS), pp. 289–303.

STOC-1986-AdlemanL #finite

Finding Irreducible Polynomials over Finite Fields (LMA, HWLJ), pp. 350–355.

STOC-1986-Barrington #bound #branch #source code

Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹ (DAMB), pp. 1–5.

STOC-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.

STOC-1986-Cai #polynomial #probability #random

With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy (JyC), pp. 21–29.

STOC-1986-KoLD #morphism #polynomial

A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract) (KIK, TJL, DZD), pp. 295–303.

ICALP-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.

CADE-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.

STOC-1985-Buss #bound #polynomial

The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract) (SRB), pp. 285–290.

STOC-1985-FichT #complexity #finite #parallel

The Parallel Complexity of Exponentiating Polynomials over Finite Fields (FEF, MT), pp. 38–47.

STOC-1985-FriedlR #algebra #polynomial #problem

Polynomial Time Solutions of Some Problems in Computational Algebra (KF, LR), pp. 153–162.

STOC-1985-Kaltofen #source code

Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors (EK), pp. 131–142.

ICALP-1985-OrponenRS #complexity #polynomial

Polynomial Levelability and Maximal Complexity Cores (PO, DAR, US), pp. 435–444.

STOC-1984-Gonnet #equivalence #polynomial #random

Determining Equivalence of Expressions in Random Polynomial Time (Extended Abstract) (GHG), pp. 334–341.

STOC-1984-Huang #algebra #finite

Factorization of Polynomials over Finite Fields and Factorization of Primes in Algebraic Number Fields (MDAH), pp. 175–182.

STOC-1984-KannanLL #algebra #polynomial

Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers (RK, AKL, LL), pp. 191–200.

STOC-1984-Karmarkar #algorithm #linear #polynomial #programming

A New Polynomial-Time Algorithm for Linear Programming (NK), pp. 302–311.

ICALP-1984-Schonhage #algorithm #integer #reduction

Factorization of Univariate Integer Polynomials by Diophantine Aproximation and an Improved Basis Reduction Algorithm (AS), pp. 436–447.

STOC-1983-Heide #algorithm #linear #polynomial #problem

A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem (FMadH), pp. 70–79.

STOC-1983-KanellakisCV #dependence #polynomial #problem

Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract) (PCK, SSC, MYV), pp. 264–277.

STOC-1983-LandauM #polynomial

Solvability by Radicals is in Polynomial Time (SL, GLM), pp. 140–151.

STOC-1983-Lenstra #finite #multi

Factoring Multivariate Polynomials over Finite Fields (Extended Abstract) (AKL), pp. 189–192.

STOC-1983-Young #polynomial #set

Some Structural Properties of Polynomial Reducibilities and Sets in NP (PY), pp. 392–401.

ICALP-1983-GathenK #finite #multi #polynomial

Polynomial-Time Factorization of Multivariate Polynomials over Finite Fields (JvzG, EK), pp. 250–263.

ICALP-1983-Lenstra #multi

Factoring Multivariate Integral Polynomials (AKL), pp. 458–465.

STOC-1982-DolevS #algorithm #multi #polynomial

Polynomial Algorithms for Multiple Processor Agreement (DD, HRS), pp. 401–407.

STOC-1982-Immerman #polynomial #query #relational

Relational Queries Computable in Polynomial Time (Extended Abstract) (NI), pp. 147–152.

STOC-1982-Kaltofen #multi #polynomial #reduction

A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization (EK), pp. 261–266.

ICALP-1982-FlajoletS #branch #polynomial #process

A Branching Process Arising in Dynamic Hashing, Trie Searching and Polynomial Factorization (PF, JMS), pp. 239–251.

GG-1982-Schnitzler #graph #morphism #problem

The isomorphism problem is polynomially solvable for certain graph languages (MS), pp. 369–379.

STOC-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.

STOC-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.

ICALP-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.

STOC-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.

STOC-1980-HeintzS #testing

Testing Polynomials which Are Easy to Compute (Extended Abstract) (JH, CPS), pp. 262–272.

STOC-1980-Tompa80a #algorithm #implementation #polynomial #sublinear #transitive

Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations (MT), pp. 333–338.

STOC-1979-Cook #polynomial

Deterministic CFL’s Are Accepted Simultaneously in Polynomial Time and Log Squared Space (SAC), pp. 338–345.

STOC-1979-GilbertLT #polynomial #problem

The Pebbling Problem is Complete in Polynomial Space (JRG, TL, RET), pp. 237–248.

STOC-1979-Long #on the #polynomial

On γ-Reducibility versus Polynomial Time Many-One Reducibility (Extended Abstract) (TJL), pp. 278–287.

ICALP-1979-Selman #behaviour #polynomial #set

P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP (ALS), pp. 546–555.

POPL-1979-LiuF #pattern matching #polynomial #string

String Pattern Matching in Polynomial Time (KCL, ACF), pp. 222–225.

STOC-1978-Hyafil #evaluation #on the #parallel

On the Parallel Evaluation of Multivariate Polynomials (LH), pp. 193–195.

STOC-1978-Pan #complexity

Computational Complexity of Computing Polynomials over the Fields of Real and Complex Numbers (VYP), pp. 162–172.

STOC-1977-SimonG #polynomial

Polynomial Reducibilities and Upward Diagonalizations (IS, JG), pp. 186–194.

ICALP-1977-PazM #approximate #nondeterminism #optimisation #polynomial #problem

Non-Deterministic Polynomial Optimization Problems and Their Approximation (AP, SM), pp. 370–379.

STOC-1976-LiptonS #evaluation

Evaluation of Polynomials with Super-Preconditioning (RJL, LJS), pp. 174–180.

STOC-1976-MandersA #polynomial #problem

NP-Complete Decision Problems for Quadratic Polynomials (KLM, LMA), pp. 23–29.

ICALP-1976-Restivo #on the #product line

On a Family of Codes Related to Factorization of Cyclotomic Polynomials (AR), pp. 38–44.

STOC-1975-EvenT #combinator #polynomial #problem

a Combinatorial Problem which is Complete in Polynomial Space (SE, RET), pp. 66–71.

STOC-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.

STOC-1975-Wotschke #polynomial #problem #recognition

Degree-Languages, Polynomial Time Recognition, and the LBA Problem (DW), pp. 145–152.

STOC-1974-BorodinC #on the

On the Number of Additions to Compute Specific Polynomials (Preliminary Version) (AB, SAC), pp. 342–347.

STOC-1974-CookS #polynomial #requirements

Storage Requirements for Deterministic Polynomial Time Recognizable Languages (SAC, RS), pp. 33–39.

STOC-1974-JonesL #polynomial #problem

Complete Problems for Deterministic Polynomial Time (NDJ, WTL), pp. 40–46.

STOC-1974-LadnerLS #polynomial

Comparisons of Polynomial-Time Reducibilities (REL, NAL, ALS), pp. 110–121.

STOC-1974-Mehlhorn #polynomial #recursion

Polynomial and Abstract Subrecursive Classes (KM), pp. 96–109.

STOC-1973-GentlemanJ #algorithm #analysis #case study

Analysis of Algorithms, a Case Study: Determinants of Polynomials (WMG, SCJ), pp. 135–141.

STOC-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.

STOC-1973-Ladner #polynomial

Polynomial Time Reducibility (REL), pp. 122–129.

SOSP-1973-Ullman #polynomial #problem #scheduling

Polynomial Complete Scheduling Problems (JDU), pp. 96–101.

STOC-1972-Fiduccia #algorithm #evaluation #fourier #performance #polynomial #revisited

Polynomial Evaluation via the Division Algorithm: The Fast Fourier Transform Revisited (CMF), pp. 88–93.