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