BibSLEIGH — polynomial tag

polynomial

polynomial

Tag #polynomial

499 papers:

CSL-2020-GanardiK #automation #equivalence: Automatic Equivalence Structures of Polynomial Growth (MG, BK), p. 16.
ICML-2019-AnconaOG #algorithm #approximate #network: Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation (MA, CÖ, MHG), pp. 272–281.
ICML-2019-HashemiGVT #information management #modelling: Submodular Observation Selection and Information Gathering for Quadratic Models (AH, MG, HV, UT), pp. 2653–2662.
ICML-2019-JainiSY: Sum-of-Squares Polynomial Flow (PJ, KAS, YY), pp. 3009–3018.
ICML-2019-RezaeiG #process: A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes (AR, SOG), pp. 5438–5447.
ICML-2019-SotoLF #3d #distributed #matrix #multi: Dual Entangled Polynomial Code: Three-Dimensional Coding for Distributed Matrix Multiplication (PS, JL, XF), pp. 5937–5945.
CASE-2019-HosseiniCD #energy #robust #scheduling #smarttech: Robust Energy Scheduling of Interconnected Smart Homes with Shared Energy Storage under Quadratic Pricing (SMH, RC, MD), pp. 966–971.
CASE-2019-SharabianiBGND #algorithm #kernel #using: A Computer-Aided System for Determining the Application Range of a Warfarin Clinical Dosing Algorithm Using Support Vector Machines with a Polynomial Kernel Function (AS, AB, WLG, RN, HD), pp. 418–423.
CASE-2019-WannerS #flexibility #programming #using: Tool-center-point control of a flexible link concrete pump with hydraulic limitations using quadratic programming (JW, OS), pp. 561–566.
DLT-2018-KoNP #integer #nondeterminism #problem #reachability: Reachability Problems in Nondeterministic Polynomial Maps on the Integers (SKK, RN, IP), pp. 465–477.
DLT-2018-OliveiraW: Intersection Non-emptiness and Hardness Within Polynomial Time (MdOO, MW), pp. 282–290.
ICML-2018-AbeilleL #bound #linear #problem: Improved Regret Bounds for Thompson Sampling in Linear Quadratic Control Problems (MA, AL), pp. 1–9.
ICML-2018-CohenHKLMT #linear #online: Online Linear Quadratic Control (AC, AH, TK, NL, YM, KT), pp. 1028–1037.
ICML-2018-DoikovR #random: Randomized Block Cubic Newton Method (ND, PR), pp. 1289–1297.
ICML-2018-DuL #network #on the #power of: On the Power of Over-parametrization in Neural Networks with Quadratic Activation (SSD, JDL), pp. 1328–1337.
ICML-2018-Fazel0KM #convergence #linear #policy: Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (MF, RG0, SMK, MM), pp. 1466–1475.
ICML-2018-GhoshalH #learning #modelling #predict: Learning Maximum-A-Posteriori Perturbation Models for Structured Prediction in Polynomial Time (AG, JH), pp. 1749–1757.
ICML-2018-TuR #difference #learning #linear: Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator (ST, BR), pp. 5012–5021.
ICML-2018-ZhouXG #probability: Stochastic Variance-Reduced Cubic Regularized Newton Method (DZ, PX0, QG), pp. 5985–5994.
ICPR-2018-BlumenthalDBBG #distance #edit distance #graph #problem: Quasimetric Graph Edit Distance as a Compact Quadratic Assignment Problem (DBB, ÉD, SB, LB, JG), pp. 934–939.
CGO-2018-AndersonG #programming: Optimal DNN primitive selection with partitioned boolean quadratic programming (AA0, DG), pp. 340–351.
CSL-2018-DasO #recursion: A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions (AD0, IO), p. 17.
IJCAR-2018-Das: Focussing, MALL and the Polynomial Hierarchy (AD0), pp. 689–705.
VMCAI-2018-HumenbergerJK #generative #invariant #multi: Invariant Generation for Multi-Path Loops with Polynomial Assignments (AH, MJ, LK), pp. 226–246.
FSCD-2017-KanovichKMS #algorithm #bound #calculus #order: A Polynomial-Time Algorithm for the Lambek Calculus with Brackets of Bounded Order (MIK, SK, GM, AS), p. 17.
FSCD-2017-KawamuraS: Polynomial Running Times for Polynomial-Time Oracle Machines (AK, FS), p. 18.
ICML-2017-KohlerL #optimisation: Sub-sampled Cubic Regularization for Non-convex Optimization (JMK, AL), pp. 1895–1904.
CASE-2017-RiaziBL #energy: From trapezoid to polynomial: Next-generation energy-efficient robot trajectories (SR, KB, BL), pp. 1191–1195.
CASE-2017-ZhaoR #approximate: Polynomial trajectory approximation along specified paths for robot manipulators (RZ, SMR), pp. 106–111.
CSL-2017-AngluinAF #learning #query: Query Learning of Derived Omega-Tree Languages in Polynomial Time (DA, TA, DF), p. 21.
CSL-2017-Grussien #graph: Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs (BG), p. 19.
DLT-2016-BoiretP #equivalence #linear #transducer: Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time (AB, RP), pp. 355–367.
DLT-2016-Paul #ambiguity #automaton #finite #on the: On Finite and Polynomial Ambiguity of Weighted Tree Automata (EP), pp. 368–379.
ICML-2016-BlondelIFU #algorithm #network #performance: Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms (MB, MI, AF, NU), pp. 850–858.
ICML-2016-LiuWS #constraints #convergence #linear #optimisation #orthogonal: Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods (HL, WW, AMCS), pp. 1158–1167.
ICML-2016-ZhangLJ #network: L1-regularized Neural Networks are Improperly Learnable in Polynomial Time (YZ0, JDL, MIJ), pp. 993–1001.
ICPR-2016-BougleuxGB #distance #edit distance #graph: Graph edit distance as a quadratic program (SB, BG, LB), pp. 1701–1706.
ICPR-2016-KhanH #adaptation #learning #using: Adapting instance weights for unsupervised domain adaptation using quadratic mutual information and subspace learning (MNAK, DRH), pp. 1560–1565.
ICPR-2016-SharabatiX #approach #performance: Fast local polynomial regression approach for speckle noise removal (WKS, BX), pp. 3198–3203.
SAS-2016-RouxVS #invariant #programming #validation: Validating Numerical Semidefinite Programming Solvers for Polynomial Invariants (PR, YLV, SS0), pp. 424–446.
CSL-2016-PakusaSS #problem: Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time (WP, SS, ES), p. 17.
IJCAR-2016-GanDXZKC #synthesis: Interpolant Synthesis for Quadratic Polynomial Inequalities and Combination with EUF (TG, LD, BX, NZ, DK, MC), pp. 195–212.
IJCAR-2016-TungKO #constraints #named #smt: raSAT: An SMT Solver for Polynomial Constraints (VXT, TVK, MO), pp. 228–237.
VMCAI-2016-SogokonGJP #generative #invariant: A Method for Invariant Generation for Polynomial Continuous Systems (AS, KG, PBJ, AP), pp. 268–288.
ECSA-2015-BelleEDKM #architecture #problem: The Layered Architecture Recovery as a Quadratic Assignment Problem (ABB, GEB, CD, SK, HM), pp. 339–354.
DLT-2015-Dehornoy #normalisation #overview: Garside and Quadratic Normalisation: A Survey (PD), pp. 14–45.
ICALP-v1-2015-FominKLPS #algorithm: Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree (FVF, PK, DL, FP, SS), pp. 494–505.
ICALP-v1-2015-Ganguly: Taylor Polynomial Estimator for Estimating Frequency Moments (SG), pp. 542–553.
ICALP-v1-2015-HenzingerKL #component: Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time (MH, SK, VL), pp. 713–724.
ICALP-v2-2015-AlistarhG #protocol: Polylogarithmic-Time Leader Election in Population Protocols (DA, RG), pp. 479–491.
ICALP-v2-2015-EtessamiSY #branch #equation #fixpoint #markov #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.
LATA-2015-AmanoS #bound #multi: A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP (KA, AS), pp. 461–472.
TLCA-2015-Redmond #parametricity #λ-calculus: Polynomial Time in the Parametric λ Calculus (BFR), pp. 288–301.
CIKM-2015-BidoitHT #performance: Efficient Computation of Polynomial Explanations of Why-Not Questions (NB, MH, AT), pp. 713–722.
ICML-2015-LeeR #distributed #linear #optimisation: Distributed Box-Constrained Quadratic Optimization for Dual Linear SVM (CPL, DR), pp. 987–996.
SAS-2015-AdjeGM #generative #invariant #optimisation #using: Property-based Polynomial Invariant Generation Using Sums-of-Squares Optimization (AA, PLG, VM), pp. 235–251.
CASE-2015-DiganiHSS #approach #coordination #multi #programming: A Quadratic Programming approach for coordinating multi-AGV systems (VD, MAH, LS, CS), pp. 600–605.
STOC-2015-AbrahamD #complexity: Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity (IA, DD), pp. 605–614.
STOC-2015-FoxKM #approximate: A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection (KF, PNK, SM), pp. 841–850.
CAV-2015-ChenHWZ #generative #invariant: Counterexample-Guided Polynomial Loop Invariant Generation by Lagrange Interpolation (YFC, CDH, BYW, LZ), pp. 658–674.
CSL-2015-GasconST #strict #unification: Two-Restricted One Context Unification is in Polynomial Time (AG, MSS, AT), pp. 405–422.
LICS-2015-GasconTS #problem #unification: One Context Unification Problems Solvable in Polynomial Time (AG, AT, MSS), pp. 499–510.
LICS-2015-GradelPSK #first-order: Characterising Choiceless Polynomial Time with First-Order Interpretations (EG, WP, SS, LK), pp. 677–688.
VMCAI-2015-AdjeG #automation #invariant #linear #source code #synthesis: Automatic Synthesis of Piecewise Linear Quadratic Invariants for Programs (AA, PLG), pp. 99–116.
ICALP-v1-2014-AllamigeonBG #algorithm #game studies: The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average (XA, PB, SG), pp. 89–100.
ICALP-v1-2014-BjorklundH: Shortest Two Disjoint Paths in Polynomial Time (AB, TH), pp. 211–222.
FM-2014-RouxG #comparison #invariant: Computing Quadratic Invariants with Min- and Max-Policy Iterations: A Practical Comparison (PR, PLG), pp. 563–578.
RTA-TLCA-2014-CarvalhoS #decidability #set: An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting (DdC, JGS), pp. 179–193.
ICPR-2014-CaoH #revisited: Quadratic Discriminant Revisited (WC, RMH), pp. 1283–1288.
ICPR-2014-Nilsson #using: Elastic Net Regularized Logistic Regression Using Cubic Majorization (MN), pp. 3446–3451.
ICPR-2014-ZhouZYL #feature model #recognition: Improving Handwritten Chinese Character Recognition with Discriminative Quadratic Feature Extraction (MKZ, XYZ, FY, CLL), pp. 244–249.
KR-2014-GottlobMP: Polynomial Combined Rewritings for Existential Rules (GG, MM, AP).
LOPSTR-2014-ChowdhuryLCKY #approximate #case study #logic programming #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.
SAS-2014-GhorbalSP #algebra #difference #equation: Invariance of Conjunctions of Polynomial Equalities for Algebraic Differential Equations (KG, AS, AP), pp. 151–167.
ASE-2014-ZhangCHXXZM #search-based: Search-based inference of polynomial metamorphic relations (JZ, JC, DH, YX, BX, LZ, HM), pp. 701–712.
CASE-2014-GunawanNPL #hybrid #metaheuristic #problem: Hybrid metaheuristics for solving the quadratic assignment problem and the generalized quadratic assignment problem (AG, KMN, KLP, HCL), pp. 119–124.
DAC-2014-WangOC #optimisation #performance #synthesis: Enabling Efficient Analog Synthesis by Coupling Sparse Regression and Polynomial Optimization (YW, MO, CC), p. 6.
DATE-2014-YasinSE #manycore: Unified, ultra compact, quadratic power proxies for multi-core processors (MY, AS, IAME), pp. 1–4.
STOC-2014-ChanDSS #approximate #estimation #performance: Efficient density estimation via piecewise polynomial approximation (SoC, ID, RAS, XS), pp. 604–613.
STOC-2014-ChekuriC #bound #theorem: Polynomial bounds for the grid-minor theorem (CC, JC), pp. 60–69.
STOC-2014-DeS #approximate #performance: Efficient deterministic approximate counting for low-degree polynomial threshold functions (AD, RAS), pp. 832–841.
STOC-2014-DvirSW: Breaking the quadratic barrier for 3-LCC’s over the reals (ZD, SS, AW), pp. 784–793.
STOC-2014-Vegh #algorithm: A strongly polynomial algorithm for generalized flow maximization (LAV), pp. 644–653.
SAT-2014-LarrazORR #constraints: Minimal-Model-Guided Approaches to Solving Polynomial Constraints and Extensions (DL, AO, ERC, AR), pp. 333–350.
SMT-2014-KhanhTO #difference #named #smt: raSAT: SMT for Polynomial Inequality (TVK, VXT, MO), p. 67.
VMCAI-2014-LeikeT #source code #synthesis: Synthesis for Polynomial Lasso Programs (JL, AT), pp. 434–452.
ICDAR-2013-ZhangL: Locally Smoothed Modified Quadratic Discriminant Function (XYZ, CLL), pp. 8–12.
ICDAR-2013-ZhouYL #learning #performance #recognition: GPU-Based Fast Training of Discriminative Learning Quadratic Discriminant Function for Handwritten Chinese Character Recognition (MKZ, FY, CLL), pp. 842–846.
PODS-2013-Gottlob #identification: Deciding monotone duality and identifying frequent itemsets in quadratic logspace (GG), pp. 25–36.
ICALP-v1-2013-DuanM #algorithm #combinator #linear: A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market (RD, KM), pp. 425–436.
ICALP-v1-2013-FilmusLMNV #bound #calculus #comprehension #towards: Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds — (YF, ML, MM, JN, MV), pp. 437–448.
ICALP-v1-2013-GlasserNRSW #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 #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 #robust: A Robust AFPTAS for Online Bin Packing with Polynomial Migration, (KJ, KMK), pp. 589–600.
ICALP-v2-2013-ChristodoulouG #game studies: Price of Stability in Polynomial Congestion Games (GC, MG), pp. 496–507.
ICALP-v2-2013-DieudonneP #approach: Deterministic Polynomial Approach in the Plane (YD, AP), pp. 533–544.
LATA-2013-Blanchet-SadriBFH #approach #graph: A Graph Polynomial Approach to Primitivity (FBS, MB, NF, JH), pp. 153–164.
KDD-2013-PhamP #kernel #performance #scalability: Fast and scalable polynomial kernels via explicit feature maps (NP, RP), pp. 239–247.
KDD-2013-SunBK #identification #optimisation: Quadratic optimization to identify highly heritable quantitative traits from complex phenotypic features (JS, JB, HRK), pp. 811–819.
PPDP-2013-YamadaKS #order #recursion: Unifying the Knuth-Bendix, recursive path and polynomial orders (AY, KK, TS), pp. 181–192.
SAC-2013-RabanalR #metaheuristic #problem #reduction #using: Using polynomial reductions to test the suitability of metaheuristics for solving NP-complete problems (PR, IR), pp. 194–199.
CASE-2013-WangSS #novel #order #problem #scheduling: A novel quadratic formulation for customer order scheduling problem (LW, ZS, LS), pp. 576–580.
CASE-2013-YueH13a #assembly #concurrent #petri net #policy #process: A polynomial deadlock avoidance policy for a class of assembly processes based on Petri nets (HY, HH), pp. 1151–1156.
CC-2013-Krause: Optimal Register Allocation in Polynomial Time (PKK), pp. 1–20.
CGO-2013-DioufCR #heuristic: A polynomial spilling heuristic: Layered allocation (BD, AC, FR), p. 10.
DATE-2013-Struzyna: Sub-quadratic objectives in quadratic placement (MS), pp. 1867–1872.
STOC-2013-BeckNT #calculus #trade-off: Some trade-off results for polynomial calculus: extended abstract (CB, JN, BT), pp. 813–822.
STOC-2013-KeevashKM: Polynomial-time perfect matchings in dense hypergraphs (PK, FK, RM), pp. 311–320.
STOC-2013-KingS: Byzantine agreement in polynomial expected time: [extended abstract] (VK, JS), pp. 401–410.
CAV-2013-ChengRS #constraints #named: JBernstein: A Validity Checker for Generalized Polynomial Constraints (CHC, HR, NS), pp. 656–661.
CAV-2013-PuggelliLSS #nondeterminism #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 #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.
ICALP-v1-2012-BabaiCQ #morphism: Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups — (LB, PC, YQ), pp. 51–62.
ICALP-v1-2012-BhaskaraCMV #on the #programming: On Quadratic Programming with a Ratio Objective (AB, MC, RM, AV), pp. 109–120.
ICALP-v1-2012-EtessamiSY #algorithm #branch #equation #markov #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: The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation) (LAG, MJ), pp. 399–410.
ICALP-v2-2012-Fiore: Discrete Generalised Polynomial Functors — (MPF), pp. 214–226.
LATA-2012-GeilkeZ #algorithm #learning #pattern matching: Polynomial-Time Algorithms for Learning Typed Pattern Languages (MG, SZ), pp. 277–288.
RTA-2012-Felgenhauer #confluence #term rewriting: Deciding Confluence of Ground Term Rewrite Systems in Cubic Time (BF), pp. 165–175.
RTA-2012-FuhsK #higher-order: Polynomial Interpretations for Higher-Order Rewriting (CF, CK), pp. 176–192.
ICPR-2012-AskKA #equation #performance #symmetry: Exploiting p-fold symmetries for faster polynomial equation solving (EA, YK, KÅ), pp. 3232–3235.
PEPM-2012-MatsudaIN #cumulative #multi #traversal: Polynomial-time inverse computation for accumulative functions with multiple data traversals (KM, KI, KN), pp. 5–14.
POPL-2012-SmaragdakisESYF #concurrent #detection #predict: Sound predictive race detection in polynomial time (YS, JE, CS, JY, CF), pp. 387–400.
PPDP-2012-Madet #multi #thread #λ-calculus: A polynomial time λ-calculus with multithreading and side effects (AM), pp. 55–66.
SAS-2012-CacheraJJK #imperative #invariant #source code: Inference of Polynomial Invariants for Imperative Programs: A Farewell to Gröbner Bases (DC, TPJ, AJ, FK), pp. 58–74.
ICSE-2012-NguyenKWF #array #dynamic analysis #invariant #using: Using dynamic analysis to discover polynomial and array invariants (TN, DK, WW, SF), pp. 683–693.
ICSE-2012-ZhouXZ #bound #named #search-based: Stride: Search-based deterministic replay in polynomial time via bounded linkage (JZ, XX, CZ), pp. 892–902.
SAC-2012-ZhaoHWA #constraints #diagrams #difference #equation: Real solution formulas of cubic and quartic equations applied to generate dynamic diagrams with inequality constraints (TZ, HH, DW, PA), pp. 94–101.
CASE-2012-ChenK #probability: Polynomial test for Stochastic Diagnosability of discrete event systems (JC, RK), pp. 521–526.
STOC-2012-BartalGK #approximate #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 #probability #process: Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars (KE, AS, MY), pp. 579–588.
STOC-2012-Vegh #algorithm #low cost #problem: Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives (LAV), pp. 27–40.
ICDAR-2011-SuLZ #learning: Perceptron Learning of Modified Quadratic Discriminant Function (THS, CLL, XYZ), pp. 1007–1011.
DLT-J-2009-BealBP11 #automaton #bound #clustering #word: A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata (MPB, MVB, DP), pp. 277–288.
AFL-2011-PramodK #towards #word: Towards Shortest Synchronizing Words in Polynomial Time (VTKP, KVK), pp. 358–367.
ICALP-v1-2011-GoldbergJ #algorithm: 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: Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth (MJJ, RS), pp. 724–735.
FM-2011-DiosP #bound #certification #memory management: Certification of Safe Polynomial Memory Bounds (JdD, RP), pp. 184–199.
HCI-DDA-2011-ZhuYZ: A Cubic Polynomial Model for Fisheye Camera (HZ, XY, JZ), pp. 684–693.
CIKM-2011-KrulisLBSS #architecture #distance #gpu #manycore: Processing the signature quadratic form distance on many-core GPU architectures (MK, JL, CB, TS, TS), pp. 2373–2376.
ICML-2011-Bylander #learning #linear #multi: Learning Linear Functions with Quadratic and Linear Multiplicative Updates (TB), pp. 505–512.
ICML-2011-RoyLM #bound #source code: From PAC-Bayes Bounds to Quadratic Programs for Majority Votes (JFR, FL, MM), pp. 649–656.
OOPSLA-2011-AdamsKMMCD: Flow-sensitive type recovery in linear-log time (MDA, AWK, JM, MM, AC, RKD), pp. 483–498.
ESOP-2011-HuntS #exponential #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: Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm (BA, JG, RM, MAS), pp. 195–204.
VLDB-2010-FanLMTWW #graph #pattern matching: Graph Pattern Matching: From Intractable to Polynomial Time (WF, JL, SM, NT, YW, YW), pp. 264–275.
DLT-J-2008-GawrychowskiKRS10 #context-free grammar: Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time (PG, DK, NR, JS), pp. 597–618.
CIAA-2010-ReidenbachS #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: Exponential Time Complexity of the Permanent and the Tutte Polynomial (HD, TH, MW), pp. 426–437.
ICALP-v1-2010-MakarychevMS #algorithm #approximate #problem #reduction: Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm (KM, RM, MS), pp. 594–604.
ICALP-v1-2010-ShpilkaV #on the #testing: On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors (AS, IV), pp. 408–419.
ICALP-v1-2010-Woodruff: Additive Spanners in Nearly Quadratic Time (DPW), pp. 463–474.
ICALP-v2-2010-Blum #lr #on the: On LR(k)-Parsers of Polynomial Size (NB), pp. 163–174.
LATA-2010-CrochemoreIKRRW #on the #string: On the Maximal Number of Cubic Runs in a String (MC, CSI, MK, JR, WR, TW), pp. 227–238.
RTA-2010-NeurauterM #integer: Polynomial Interpretations over the Reals do not Subsume Polynomial Interpretations over the Integers (FN, AM), pp. 243–258.
CHI-2010-StavnessLF #named: pCubee: a perspective-corrected handheld cubic display (IS, BL, SF), pp. 1381–1390.
ICPR-2010-Cevikalp #distance #learning #metric #programming: Semi-supervised Distance Metric Learning by Quadratic Programming (HC), pp. 3352–3355.
ICPR-2010-PernekH #problem #re-engineering: Perspective Reconstruction and Camera Auto-Calibration as Rectangular Polynomial Eigenvalue Problem (ÁP, LH), pp. 49–52.
SAS-2010-GawlitzaS #semantics: Computing Relaxed Abstract Semantics w.r.t. Quadratic Zones Precisely (TMG, HS), pp. 271–286.
SAC-2010-FunfzigMF: Polytope-based computation of polynomial ranges (CF, DM, SF), pp. 1247–1252.
LDTA-J-2007-ScottJ #parsing #recognition: Recognition is not parsing — SPPF-style parsing from cubic recognisers (ES, AJ), pp. 55–70.
PDP-2010-TaktakED #algorithm #network: A Polynomial Algorithm to Prove Deadlock-Freeness of Wormhole Networks (ST, EE, JLD), pp. 121–128.
ESOP-2010-HoffmannH #analysis: Amortized Resource Analysis with Polynomial Potential (JH, MH), pp. 287–306.
STOC-2010-Aaronson: BQP and the polynomial hierarchy (SA), pp. 141–150.
STOC-2010-BurgisserC #equation #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 #satisfiability: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (HD, DvM), pp. 251–260.
STOC-2010-DiakonikolasHKMRST #bound: 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: On the structure of cubic and quartic polynomials (EH, AS), pp. 331–340.
STOC-2010-MekaZ #generative #pseudo: Pseudorandom generators for polynomial threshold functions (RM, DZ), pp. 427–436.
STOC-2010-Patrascu #bound #problem #towards: Towards polynomial lower bounds for dynamic problems (MP), pp. 603–610.
IJCAR-2010-NeurauterMZ: Monotonicity Criteria for Polynomial Interpretations over the Naturals (FN, AM, HZ), pp. 502–517.
LICS-2010-Grohe #fixpoint #graph: Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors (MG), pp. 179–188.
LICS-2010-Laubner #graph: Capturing Polynomial Time on Interval Graphs (BL), pp. 199–208.
PODS-2009-Parys #complexity #evaluation #linear #xpath: XPath evaluation in linear time with polynomial combined complexity (PP), pp. 55–64.
DLT-2009-BealP #automaton #bound #clustering #word: A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata (MPB, DP), pp. 81–90.
ICALP-v2-2009-BrancoP #equation #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: A Smooth Combination of Linear and Herbrand Equalities for Polynomial Time Must-Alias Analysis (HS, VV, VV), pp. 644–659.
RTA-2009-AvanziniM #dependence #order: Dependency Pairs and Polynomial Path Orders (MA, GM), pp. 48–62.
ICML-2009-KolterN: Near-Bayesian exploration in polynomial time (JZK, AYN), pp. 513–520.
ICML-2009-SzitaL #learning: Optimistic initialization and greediness lead to polynomial time learning in factored MDPs (IS, AL), pp. 1001–1008.
DAC-2009-HuLA #approximate: 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 #using: Polynomial datapath optimization using partitioning and compensation heuristics (OS, BA, MF), pp. 931–936.
DATE-2009-GopalakrishnanK #algebra #synthesis: Algebraic techniques to enhance common sub-expression elimination for polynomial system synthesis (SG, PK), pp. 1452–1457.
DATE-2009-WangCTHR #modelling #optimisation #performance #using: An efficient decoupling capacitance optimization using piecewise polynomial models (XW, YC, SXDT, XH, JR), pp. 1190–1195.
FoSSaCS-2009-BonsangueRS #algebra #theorem: A Kleene Theorem for Polynomial Coalgebras (MMB, JJMMR, AS), pp. 122–136.
STOC-2009-BabaiBS #matrix: Polynomial-time theory of matrix groups (LB, RB, ÁS), pp. 55–64.
CADE-2009-BorrallerasLNRR #linear #satisfiability: Solving Non-linear Polynomial Arithmetic via SAT Modulo Linear Arithmetic (CB, SL, RNM, ERC, AR), pp. 294–305.
CAV-2009-DangS #image #using: Image Computation for Polynomial Dynamical Systems Using the Bernstein Expansion (TD, DS), pp. 219–232.
CSL-2009-Grohe #fixpoint: Fixed-Point Definability and Polynomial Time (MG), pp. 20–23.
LICS-2009-BonsangueRS #algebra: An Algebra for Kripke Polynomial Coalgebras (MMB, JJMMR, AS), pp. 49–58.
DLT-2008-GawrychowskiKRS #context-free grammar: Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time (PG, DK, NR, JS), pp. 339–358.
ICALP-A-2008-BaswanaGSU #constant #distance #fault #graph: Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error (SB, AG, SS, JU), pp. 609–621.
ICALP-A-2008-BodlaenderDFH #kernel #on the #problem: On Problems without Polynomial Kernels (HLB, RGD, MRF, DH), pp. 563–574.
ICALP-A-2008-FrandsenS #normalisation: Dynamic Normal Forms and Dynamic Characteristic Polynomial (GSF, PS), pp. 434–446.
ICALP-A-2008-IwamaNPRY #linear #network: Polynomial-Time Construction of Linear Network Coding (KI, HN, MP, RR, SY), pp. 271–282.
ICALP-C-2008-HirtNP #communication #multi: Asynchronous Multi-Party Computation with Quadratic Communication (MH, JBN, BP), pp. 473–485.
RTA-2008-MoserS #proving #using: Proving Quadratic Derivational Complexities Using Context Dependent Interpretations (GM, AS), pp. 276–290.
SOFTVIS-2008-ThompsonPAH #visualisation: Visualizing the computation tree of the Tutte Polynomial (BT, DJP, CA, GH), pp. 211–212.
ICPR-2008-GaoL #classification #recognition: Combining quadratic classifier and pair discriminators by pairwise coupling for handwritten Chinese character recognition (TFG, CLL), pp. 1–4.
ICPR-2008-RiveraCT #image #programming #segmentation: Image segmentation by convex quadratic programming (MR, ODC, JT), pp. 1–5.
SEKE-2008-ChenLMW #algorithm #case study #optimisation #problem #verification: Verification of Optimization Algorithms: a Case Study of a Quadratic Assignment Problem Solver (TYC, HL, RGM, DW), pp. 16–21.
PPDP-2008-MarionP #complexity: Characterizations of polynomial complexity classes with a better intensionality (JYM, RP), pp. 79–88.
SAS-2008-SeidlFP #equation: Analysing All Polynomial Equations in ℤ₂ᵂ (HS, AF, MP), pp. 299–314.
CASE-2008-ChuCSC #algorithm: An O(T3) Polynomial algorithm for crude oil transportation (FC, CC, QS, HC), pp. 303–308.
DAC-2008-QianR #logic #probability #robust #synthesis: The synthesis of robust polynomial arithmetic with stochastic logic (WQ, MDR), pp. 648–653.
DATE-2008-MasrurDF #testing: Improvements in Polynomial-Time Feasibility Testing for EDF (AM, SD, GF), pp. 1033–1038.
DATE-2008-ZengC #analysis #random: Deep Submicron Interconnect Timing Model with Quadratic Random Variable Analysis (JKZ, CPC), pp. 1091–1094.
STOC-2008-CaiCL #bound #exclamation #problem: A quadratic lower bound for the permanent and determinant problem over any characteristic != 2 (JyC, XC, DL), pp. 491–498.
STOC-2008-ShpilkaV #testing: Read-once polynomial identity testing (AS, IV), pp. 507–516.
STOC-2008-Umans #composition #performance: Fast polynomial factorization and modular composition in small characteristic (CU), pp. 481–490.
LICS-2008-Riis #calculus #complexity #on the #proving: On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity (SR), pp. 272–283.
ICDAR-2007-YangJHH #kernel #online #recognition: Kernel Modified Quadratic Discriminant Function for Online Handwritten Chinese Characters Recognition (DY, LJ, QH, TH), pp. 38–42.
PODS-2007-FiliotNTT #xpath: Polynomial time fragments of XPath with variables (EF, JN, JMT, ST), pp. 205–214.
ICALP-2007-BlaserD #complexity: Complexity of the Cover Polynomial (MB, HD), pp. 801–812.
TLCA-2007-Baillot #linear #logic #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 Size Analysis of First-Order Functions (OS, RvK, MCJDvE), pp. 351–365.
IFL-2007-MorazanS: Optimal λ Lifting in Quadratic Time (MTM, UPS), pp. 37–56.
KDD-2007-YeJC #analysis #kernel #learning #matrix #programming: Learning the kernel matrix in discriminant analysis via quadratically constrained quadratic programming (JY, SJ, JC), pp. 854–863.
SAC-2007-SarfrazR #algorithm #image #random #using: A randomized knot insertion algorithm for outline capture of planar images using cubic spline (MS, AR), pp. 71–75.
DAC-2007-ViswanathanNAVRC #named: RQL: Global Placement via Relaxed Quadratic Spreading and Linearization (NV, GJN, CJA, PV, HR, CCNC), pp. 453–458.
DATE-2007-BonziniP #automation #set: Polynomial-time subgraph enumeration for automated instruction set extension (PB, LP), pp. 1331–1336.
DATE-2007-MuellerGS #design #programming #trade-off #using: Trade-off design of analog circuits using goal attainment and “Wave Front” sequential quadratic programming (DM, HEG, US), pp. 75–80.
FoSSaCS-2007-MarnetteKR #bound #constraints #set: Polynomial Constraints for Sets with Cardinality Bounds (BM, VK, MCR), pp. 258–273.
STOC-2007-AnshelevichK #3d #graph: Terminal backup, 3D matching, and covering cubic graphs (EA, AK), pp. 391–400.
STOC-2007-ChuzhoyK #problem: Polynomial flow-cut gaps and hardness of directed cut problems (JC, SK), pp. 179–188.
STOC-2007-GoldbergJ: Inapproximability of the Tutte polynomial (LAG, MJ), pp. 459–468.
STOC-2007-HavivR #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: On the convergence of Newton’s method for monotone systems of polynomial equations (SK, ML, JE), pp. 217–226.
SAT-2007-Buresh-OppenheimM: Minimum 2CNF Resolution Refutations in Polynomial Time (JBO, DGM), pp. 300–313.
SAT-2007-FuhsGMSTZ #analysis #satisfiability #termination: SAT Solving for Termination Analysis with Polynomial Interpretations (CF, JG, AM, PSK, RT, HZ), pp. 340–354.
SAT-2007-Kullmann #invariant #matrix #satisfiability: Polynomial Time SAT Decision for Complementation-Invariant Clause-Sets, and Sign-non-Singular Matrices (OK), pp. 314–327.
PODS-2006-GottlobN: Data exchange: computing cores in polynomial time (GG, AN), pp. 40–49.
DLT-2006-GlasserTW: Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy (CG, SDT, KWW), pp. 408–419.
ICML-2006-RavikumarL #estimation #markov #metric #programming #random: Quadratic programming relaxations for metric labeling and Markov random field MAP estimation (PDR, JDL), pp. 737–744.
ICPR-v2-2006-Liu #classification #feature model #recognition #using: High Accuracy Handwritten Chinese Character Recognition Using Quadratic Classifiers with Discriminative Feature Extraction (CLL), pp. 942–945.
ICPR-v3-2006-JiangDL #locality #programming: Convex Quadratic Programming for Object Localization (HJ, MSD, ZNL), pp. 24–27.
KDD-2006-Jaroszewicz: Polynomial association rules with applications to logistic regression (SJ), pp. 586–591.
LOPSTR-2006-NguyenS #automation #named #proving #termination: Polytool: Proving Termination Automatically Based on Polynomial Interpretations (MTN, DDS), pp. 210–218.
CASE-2006-LopatinY #algorithm #approximate #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: Optimal Polynomial Complexity Deadlock Avoidance Policies for Manufacturing Systems with Flexible Routings (KX, FT, HX, BH), pp. 448–453.
DAC-2006-WongB #multi #performance: Multi-shift quadratic alternating direction implicit iteration for high-speed positive-real balanced truncation (NW, VB), pp. 257–260.
STOC-2006-AharonovJL #algorithm #approximate #quantum: A polynomial quantum algorithm for approximating the Jones polynomial (DA, VJ, ZL), pp. 427–436.
STOC-2006-KelnerS #algorithm #linear #programming #random: A randomized polynomial-time simplex algorithm for linear programming (JAK, DAS), pp. 51–60.
CAV-2006-RoyZFH #consistency #memory management #performance #verification: Fast and Generalized Polynomial Time Memory Consistency Verification (AR, SZ, CJF, JCH), pp. 503–516.
IJCAR-2006-BaaderLS #named #ontology: CEL — A Polynomial-Time Reasoner for Life Science Ontologies (FB, CL, BS), pp. 287–291.
ICDAR-2005-LiuD #classification #multi #recognition #using: Handwritten Character Recognition Using Gradient Feature and Quadratic Classifier with Multiple Discrimination Schemes (HL, XD), pp. 19–25.
ICDAR-2005-MitomaUS #online #recognition: Online Character Recognition Based on Elastic Matching and Quadratic Discrimination (HM, SU, HS), pp. 36–40.
DLT-J-2004-BorchertLSTT05: The dot-depth and the polynomial hierarchies correspond on the delta levels (BB, KJL, FS, PT, DT), pp. 625–644.
DLT-2005-Kortelainen #generative #recursion: Polynomial Generators of Recursively Enumerable Languages (JK), pp. 320–326.
ICALP-2005-DattaDMST #logic #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 #random: Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines (SD, DvM), pp. 982–993.
ICALP-2005-Kayal #equation #finite: Solvability of a System of Bivariate Polynomial Equations over a Finite Field (NK), pp. 551–562.
ICALP-2005-Kovacs #multi: Polynomial Time Preemptive Sum-Multicoloring on Paths (AK), pp. 840–852.
DAC-2005-ZhangCHGC #analysis #statistics: Correlation-preserved non-gaussian statistical timing analysis with quadratic timing model (LZ, WC, YH, JAG, CCPC), pp. 83–88.
DATE-2005-MartensG #integration #orthogonal #simulation #using: Time-Domain Simulation of Sampled Weakly Nonlinear Systems Using Analytical Integration and Orthogonal Polynomial Series (EM, GGEG), pp. 120–125.
STOC-2005-AlonMMN #graph: Quadratic forms on graphs (NA, KM, YM, AN), pp. 486–493.
STOC-2005-Basu #algebra #algorithm #set: Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities (SB), pp. 313–322.
STOC-2005-DvirS #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 #quantum: Polynomial time quantum algorithm for the computation of the unit group of a number field (AS, UV), pp. 475–480.
SAT-J-2004-GalesiK05 #rank #satisfiability: Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank (NG, OK), pp. 89–104.
CSL-2005-SchurmannS #identification #recursion: Identifying Polynomial-Time Recursive Functions (CS, JS), pp. 525–540.
ICLP-2005-NguyenS #analysis #logic programming #source code #termination: Polynomial Interpretations as a Basis for Termination Analysis of Logic Programs (MTN, DDS), pp. 311–325.
LICS-2005-Leroux #diagrams #synthesis: A Polynomial Time Presburger Criterion and Synthesis for Number Decision Diagrams (JL), pp. 147–156.
VMCAI-2005-BradleyMS #source code #termination: Termination of Polynomial Programs (ARB, ZM, HBS), pp. 113–129.
DRR-2004-ShinJKKK #adaptation #image #using: Block-adaptive binarization of business card images in PDA using modified quadratic filter (KTS, IHJ, NCK, CHK, TSK), pp. 92–101.
DLT-2004-BorchertLSTT: The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels (BB, KJL, FS, PT, DT), pp. 89–101.
ICALP-2004-Midrijanis #bound #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: Nonparametric classification with polynomial MPMC cascades (SMB, MB, GZG).
ICPR-v3-2004-DePiero #bound #graph #memory management #worst-case: Structural Graph Matching With Polynomial Bounds On Memory and on Worst-Case Effort (FWD), pp. 379–382.
ICPR-v4-2004-KobayashiO #higher-order #identification #multi #using: Action and Simultaneous Multiple-Person Identification Using Cubic Higher-Order Local Auto-Correlation (TK, NO), pp. 741–744.
ICPR-v4-2004-NumadaNKKT #image #using: Sharpening of CT Images by Cubic Interpolation using B-Spline (MN, TN, KK, HK, HT), pp. 701–704.
KR-2004-BaralE #algorithm #policy: A Polynomial-Time Algorithm for Constructing k-Maintainable Policies (CB, TE), pp. 720–730.
SIGIR-2004-KokiopoulouS #information retrieval #semantics: Polynomial filtering in latent semantic indexing for information retrieval (EK, YS), pp. 104–111.
POPL-2004-Fiore #morphism #recursion: Isomorphisms of generic recursive polynomial types (MPF), pp. 77–88.
SAS-2004-GulwaniN #algorithm: A Polynomial-Time Algorithm for Global Value Numbering (SG, GCN), pp. 212–227.
SAS-2004-Rodriguez-CarbonellK #abstract interpretation #approach #automation #generative #invariant: An Abstract Interpretation Approach for Automatic Generation of Polynomial Invariants (ERC, DK), pp. 280–295.
DAC-2004-ObermeierJ #using: Quadratic placement using an improved timing model (BO, FMJ), pp. 705–710.
DATE-v1-2004-RaudvereSSJ #abstraction #verification: Polynomial Abstraction for Verification of Sequentially Implemented Combinational Circuits (TR, AKS, IS, AJ), pp. 690–691.
DATE-v1-2004-ZhanS #optimisation #programming #using: Optimization of Integrated Spiral Inductors Using Sequential Quadratic Programming (YZ, SSS), pp. 622–629.
FoSSaCS-2004-BaillotM #λ-calculus: Soft λ-Calculus: A Language for Polynomial Time Computation (PB, VM), pp. 27–41.
STOC-2004-Ajtai: A conjecture about polynomial time computable lattice-lattice functions (MA), pp. 486–493.
STOC-2004-DunaganV #algorithm #linear #source code: A simple polynomial-time rescaling algorithm for solving linear programs (JD, SV), pp. 315–320.
LICS-2004-BaillotT #λ-calculus: Light Types for Polynomial Time Computation in λ-Calculus (PB, KT), pp. 266–275.
SAT-2004-GalesiK #rank #satisfiability: Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank (NG, OK), pp. 76–85.
ICALP-2003-XieDI #equation #infinity #verification: A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems (GX, ZD, OHI), pp. 668–680.
DAC-2003-DongR #reduction: Piecewise polynomial nonlinear model reduction (ND, JSR), pp. 484–489.
DATE-2003-WangZ #analysis: Transistor-Level Static Timing Analysis by Piecewise Quadratic Waveform Matching (ZW, JZ), pp. 11026–11031.
FoSSaCS-2003-BournezCNM #parallel: Computability over an Arbitrary Structure. Sequential and Parallel Polynomial Time (OB, FC, PJdN, JYM), pp. 185–199.
STOC-2003-AzarCFKR: Optimal oblivious routing in polynomial time (YA, EC, AF, HK, HR), pp. 383–388.
STOC-2003-BeierV #random: Random knapsack in expected polynomial time (RB, BV), pp. 232–241.
STOC-2003-KabanetsI #bound #proving #testing: Derandomizing polynomial identity tests means proving circuit lower bounds (VK, RI), pp. 355–364.
STOC-2003-ODonnellS #bound: New degree bounds for polynomial threshold functions (RO, RAS), pp. 325–334.
ICLP-2003-Rao: Polynomial-Time Learnability from Entailment (MRKKR), pp. 489–491.
LICS-2003-Oliva #algorithm #effectiveness #proving: Polynomial-time Algorithms from Ineffective Proofs (PO), pp. 128–137.
CIAA-2002-Trahtman #algorithm #testing: A Polynomial Time Algorithm for Left [Right] Local Testability (ANT), pp. 203–212.
DLT-2002-DiekertK #equation: A Remark about Quadratic Trace Equations (VD, MK), pp. 59–66.
ICALP-2002-CzumajLZ #approximate #design #network #problem: Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem (AC, AL, HZ), pp. 973–984.
FLOPS-2002-DanvyS #λ-calculus: λ-Lifting in Quadratic Time (OD, UPS), pp. 134–151.
ICML-2002-FitzgibbonDA #approximate #monte carlo: Univariate Polynomial Inference by Monte Carlo Message Length Approximation (LJF, DLD, LA), pp. 147–154.
ICPR-v2-2002-ErcilB #classification #using: One Class Classification Using Implicit Polynomial Surface Fitting (AE, BB), pp. 152–155.
ICPR-v2-2002-VeeramachaneniFLN #classification: Style-Conscious Quadratic Field Classifier (SV, HF, CLL, GN), pp. 72–75.
ICPR-v4-2002-CollingsKN #approach #image: A Piecewise Quadratic Approach to Single Image Shape from Shading (SC, RK, LN), p. 126–?.
ICPR-v4-2002-LiuSF #classification #learning: Learning Quadratic Discriminant Function for Handwritten Character Classification (CLL, HS, HF), pp. 44–47.
PLDI-2002-DasLS #named #verification: ESP: Path-Sensitive Program Verification in Polynomial Time (MD, SL, MS), pp. 57–68.
SAS-2002-Lee #analysis: Finiteness Analysis in Polynomial Time (CSL), pp. 493–508.
SAS-2002-Muller-OlmS #decidability: Polynomial Constants Are Decidable (MMO, HS), pp. 4–19.
SAC-2002-FuC #network: Cycle embedding in faulty hierarchical cubic networks (JSF, GHC), pp. 860–864.
GPCE-2002-Lee #analysis #termination: Program Termination Analysis in Polynomial Time (CSL), pp. 218–235.
DATE-2002-HuangTXWL #algorithm #problem: A Polynomial Time Optimal Diode Insertion/Routing Algorithm for Fixing Antenna Problem (LDH, XT, HX, DFW, IML), pp. 470–475.
STOC-2002-BarakL #simulation #strict: Strict polynomial-time in simulation and extraction (BB, YL), pp. 484–493.
STOC-2002-CryanD #algorithm #approximate #constant: 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 #problem #quantum: Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem (SH), pp. 653–658.
ICLP-2002-PearceSSTW #logic programming #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 #term rewriting: Deciding Confluence of Certain Term Rewriting Systems in Polynomial Time (AT), p. 447–?.
ICALP-2001-KiayiasY #game studies: Secure Games with Polynomial Expressions (AK, MY), pp. 939–950.
ESOP-2001-Mitchell #analysis #calculus #probability #process #protocol #security: Probabilistic Polynomial-Time Process Calculus and Security Protocol Analysis (JCM), pp. 23–29.
ESOP-2001-NielsonS #analysis #control flow: Control-Flow Analysis in Cubic Time (FN, HS), pp. 252–268.
STOC-2001-Grohe: Computing crossing numbers in quadratic time (MG), pp. 231–236.
STOC-2001-JerrumSV #algorithm #approximate #matrix: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (MJ, AS, EV), pp. 712–721.
STOC-2001-Shparlinski #approximate #finite: Sparse polynomial approximation in finite fields (IS), pp. 209–215.
STOC-2001-SpielmanT #algorithm #analysis #why: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time (DAS, SHT), pp. 296–305.
STOC-2001-Valiant #quantum: Quantum computers that can be simulated classically in polynomial time (LGV), pp. 114–123.
CSL-2001-Mogbil #commutative #correctness #logic: Quadratic Correctness Criterion for Non-commutative Logic (VM), pp. 69–83.
WLC-2000-MargolisS: Power Semigroups and Polynomial Closure (SWM, BS), pp. 311–322.
CHI-2000-FrohlichP #3d: The cubic mouse: a new device for three-dimensional input (BF, JP), pp. 526–531.
ICML-2000-CampbellTB #network #reduction: Dimension Reduction Techniques for Training Polynomial Networks (WMC, KT, SVB), pp. 119–126.
ICPR-v2-2000-Kawatani #normalisation #recognition: Handwritten Kanji Recognition with Determinant Normalized Quadratic Discriminant Function (TK), pp. 2343–2346.
ICPR-v2-2000-MiyamotoHM #classification #design #using: Use of Bootstrap Samples in Quadratic Classifier Design (TM, YH, YM), pp. 2789–2792.
STOC-2000-GurvitsS #algorithm #approximate: A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume (LG, AS), pp. 48–57.
STOC-2000-IwataFF #algorithm #combinator: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions (SI, LF, SF), pp. 97–106.
STOC-2000-KenyonSY #approximate: Polynomial-time approximation scheme for data broadcast (CK, NS, NEY), pp. 659–666.
STOC-2000-LiMW #multi: Near optimal multiple alignment within a band in polynomial time (ML, BM, LW), pp. 425–434.
CSL-2000-BlassG00a: Choiceless Polynomial Time Computation and the Zero-One Law (AB, YG), pp. 18–40.
LICS-2000-AehligS #analysis: A Syntactical Analysis of Non-Size-Increasing Polynomial Time Computation (KA, HS), pp. 84–91.
ICALP-1999-OlshevskyP #evaluation #matrix: Polynomial and Rational Evaluation and Interpolation (with Structured Matrices) (VO, VYP), pp. 585–594.
FM-v1-1999-LincolnMMS #analysis #equivalence #probability #security: Probabilistic Polynomial-Time Equivalence and Security Analysis (PL, JCM, MM, AS), pp. 776–793.
RTA-1999-FrougnyS #term rewriting: A Rewrite System Associated with Quadratic Pisot Units (CF, JS), pp. 356–370.
SAC-1999-Bugarin #approximate #linear: Linear Quadratic Approximation for Solving a Model Economy Distorted by Progressive Taxation (MNSB), pp. 52–56.
DATE-1999-SmithM #component: Polynomial Methods for Allocating Complex Components (JS, GDM), pp. 217–222.
FoSSaCS-1999-DantsinV #algorithm #nondeterminism #set #unification: A Nondeterministic Polynomial-Time Unification Algorithm for Bags, Sets and Trees (ED, AV), pp. 180–196.
STOC-1999-BussGIP #calculus #linear: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (SRB, DG, RI, TP), pp. 547–556.
STOC-1999-ChenM #approximate #multi #scheduling: A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (JC, AM), pp. 418–427.
STOC-1999-JansenSS #approximate: Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme (KJ, RSO, MS), pp. 394–399.
STOC-1999-KlivansM #graph #morphism #proving: Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (AK, DvM), pp. 659–667.
STOC-1999-NaorP #evaluation: Oblivious Transfer and Polynomial Evaluation (MN, BP), pp. 245–254.
STOC-1999-Schaefer #graph: Graph Ramsey Theory and the Polynomial Hierarchy (MS), pp. 592–601.
STOC-1999-Wayne #algorithm #combinator: A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow (KDW), pp. 11–18.
LICS-1999-Hofmann99a #linear: Linear Types and Non-Size-Increasing Polynomial Time Computation (MH0), pp. 464–473.
ICALP-1998-CzumajL #approximate: A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity (AC, AL), pp. 682–694.
ICALP-1998-DyerG #algorithm: A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables (MED, CSG), pp. 339–350.
ICPR-1998-SakaiYH #robust: A new robust quadratic discriminant function (MS, MY, HH), pp. 99–102.
ICPR-1998-SuriHS #automation #bound #classification: Automatic quadratic calibration for correction of pixel classification boundaries to an accuracy of 2.5 millimeters: an application in cardiac imaging (JSS, RMH, FHS), pp. 30–33.
DAC-1998-ParakhBS: Congestion Driven Quadratic Placement (PNP, RBB, KAS), pp. 275–278.
DATE-1998-ChuW #algorithm: A Polynomial Time Optimal Algorithm for Simultaneous Buffer and Wire Sizing (CCNC, DFW), pp. 479–485.
STOC-1998-LewinV #question #towards: Checking Polynomial Identities over any Field: Towards a Derandomization? (DL, SPV), pp. 438–447.
STOC-1998-LinialSW #algorithm #approximate #matrix #scalability: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents (NL, AS, AW), pp. 644–652.
STOC-1998-MourrainP #equation #multi: Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations (BM, VYP), pp. 488–496.
STOC-1998-NatanzonSS #algorithm #approximate #problem: A Polynomial Approximation Algorithm for the Minimum Fill-In Problem (AN, RS, RS), pp. 41–47.
CSL-1998-BonfanteCMT #complexity #term rewriting: Complexity Classes and Rewrite Systems with Polynomial Interpretation (GB, AC, JYM, HT), pp. 372–384.
ICDAR-1997-FrankeGKM #classification #comparison #markov #modelling #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.
ICDAR-1997-TangLY #approach #automation #documentation #image: Quadratic Spline Wavelet Approach to Automatic Extraction of Baselines from Document Images (YYT, JL, LY), pp. 693–696.
RTA-1997-BachmairT #commutative: D-Bases for Polynomial Ideals over Commutative Noetherian Rings (LB, AT), pp. 113–127.
ICML-1997-MooreSD #performance #predict: Efficient Locally Weighted Polynomial Regression Predictions (AWM, JGS, KD), pp. 236–244.
SAS-1997-Braunburger #analysis #automation #order #termination #using: Automatic Termination Analysis for Partial Functions Using Polynomial Orderings (JB), pp. 330–344.
SAS-1997-Frey #type system: Satisfying Subtype Inequalities in Polynomial Space (AF), pp. 265–277.
SAC-1997-FeinsilverGS #approach #on the: On the computation of polynomial representations of nilpotent Lie groups: a symbolic mathematical approach (PF, UG, RS), pp. 537–539.
DAC-1997-AlpertCHMY #revisited: Quadratic Placement Revisited (CJA, TFC, DJHH, ILM, KY), pp. 752–757.
PDP-1997-DesaiG #network: Generalized cubic networks (KRD, KG), pp. 116–126.
STOC-1997-AsanoKTT #approximate #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: Approximate Complex Polynomial Evaluation in Near Constant Work Per Point (JHR), pp. 30–39.
LICS-1997-HeintzeM #analysis #on the #type system: On the Cubic Bottleneck in Subtyping and Flow Analysis (NH, DAM), pp. 342–351.
ICALP-1996-Fernandez-BacaL #algorithm: A Polynomial-Time Algorithm for Near-Perfect Phylogeny (DFB, JL), pp. 670–680.
ICALP-1996-FlajoletGP #random: Random Polynomials and Polynomial Factorization (PF, XG, DP), pp. 232–243.
WIA-1996-PontyZC #algorithm #automaton #regular expression: A New Quadratic Algorithm to Convert a Regular Expression into an Automaton (JLP, DZ, JMC), pp. 109–119.
ICPR-1996-Molina-GamezS #approach #recognition: Sparse groups: A polynomial middle-level approach for object recognition (MCMG, JBSV), pp. 518–522.
SAS-1996-Givan #specification: Inferring Program Specifications in Polynomial-Time (RG), pp. 205–219.
PDP-1996-Larriba-Pey #parallel: Vector and Parallel Interpolation by Natural Cubic Splines and B-Splines (JLLP), pp. 385–393.
CADE-1996-HermannK #algorithm #unification: Unification Algorithms Cannot be Combined in Polynomial Time (MH, PGK), pp. 246–260.
CAV-1996-Baier #algorithm #bisimulation #probability #simulation #testing: Polynomial Time Algorithms for Testing Probabilistic Bisimulation and Simulation (CB), pp. 50–61.
LICS-1996-Narendran #equation #linear: Solving Linear Equations over Polynomial Semirings (PN), pp. 466–472.
ICALP-1995-Ambos-Spies #approximate #on the: On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (KAS), pp. 384–392.
ICALP-1995-PinW #ambiguity: Polynomial Closure and Unambiguous Product (JÉP, PW), pp. 348–359.
RTA-1995-Giesl #generative #order #proving #termination: Generating Polynomial Orderings for Termination Proofs (JG), pp. 426–431.
RTA-1995-Senizergues #algorithm #confluence #testing: A Polynomial Algorithm Testing Partial Confluence of Basic Semi-Thue Systems (GS), pp. 194–209.
SAS-1995-DussartHM #analysis #polymorphism #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 #problem: Polynomial time approximation schemes for dense instances of NP-hard problems (SA, DRK, MK), pp. 284–293.
STOC-1995-HannenhalliP #algorithm #permutation #sorting: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals (SH, PAP), pp. 178–189.
STOC-1995-Karger #approximate #network #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 bounds for VC dimension of sigmoidal neural networks (MK, AM), pp. 200–208.
STOC-1995-KushilevitzOR #communication: Log-space polynomial end-to-end communication (EK, RO, AR), pp. 559–568.
STOC-1995-Pan #algorithm #approximate #parallel: Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros (VYP), pp. 741–750.
STOC-1995-Reif #parallel #performance: Work efficient parallel solution of Toeplitz systems and polynomial GCD (JHR), pp. 751–761.
TAPSOFT-1995-BadouelBD #algorithm #bound #synthesis: Polynomial Algorithms for the Synthesis of Bounded Nets (EB, LB, PD), pp. 364–378.
TAPSOFT-1995-WilkeY #infinity #regular expression #word: Computing the Wadge Degree, the Lifschitz Degree, and the Rabin Index of a Regular Language of Infinite Words in Polynomial Time (TW, HY), pp. 288–302.
ICALP-1994-HoftingW #analysis #graph: Polynomial Time Analysis of Torodial Periodic Graphs (FH, EW), pp. 544–555.
ICALP-1994-Pin #set: Polynomial Closure of Group Languages and Open Sets of the Hall Topology (JÉP), pp. 424–435.
STOC-1994-AroraRV #simulation: Simulating quadratic dynamical systems is PSPACE-complete (SA, YR, UVV), pp. 459–467.
ICDAR-1993-Kawatani #learning #recognition: Handprinted numeral recognition with the learning quadratic discriminant function (TK), pp. 14–17.
RTA-1993-Plaisted #constraints #termination #testing: Polynomial Time Termination and Constraint Satisfaction Tests (DAP), pp. 405–420.
DAC-1993-HuangPS #approach #approximate #heuristic #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 #using: S-Parameter Based Macro Model of Distributed-Lumped Networks Using Exponentially Decayed Polynomial Function (HL, WWMD, RW, FYC), pp. 726–731.
DAC-1993-ShihK #clustering #programming: Quadratic Boolean Programming for Performance-Driven System Partitioning (MS, ESK), pp. 761–765.
STOC-1993-GarayM: Fully polynomial Byzantine agreement in t+1 rounds (JAG, YM), pp. 31–41.
STOC-1993-Goldberg #algorithm #graph #product line: Polynomial space polynomial delay algorithms for listing families of graphs (LAG), pp. 218–225.
ILPS-1993-PesantB #constraints #geometry: Handling Quadratic Constraints through Geometry (GP, MB), p. 659.
ICALP-1992-DietzfelbingerGMP #reliability: Polynomial Hash Functions Are Reliable (MD, JYG, YM, NP), pp. 235–246.
ICALP-1992-KarhumakiPR #context-free grammar #testing: Polynomial Size Test Sets for Context-Free Languages (JK, WP, WR), pp. 53–64.
STOC-1992-AdlerB #algebra #algorithm #linear #programming: Polynomial Algorithms for Linear Programming over the Algebraic Numbers (IA, PAB), pp. 483–494.
STOC-1992-Barvinok #equation #testing: Feasibility Testing for Systems of Real Quadratic Equations (AIB), pp. 126–132.
CADE-1992-CichonL #algorithm #complexity: Polynomial Interpretations and the Complexity of Algorithms (AC, PL), pp. 139–147.
CSL-1992-Stewart #bound #logic #query: Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machines (IAS), pp. 410–424.
PODS-1991-AfratiCY #datalog #on the: On Datalog vs. Polynomial Time (FNA, SSC, MY), pp. 13–25.
ICALP-1991-Loebl #graph #performance: Efficient Maximal Cubic Graph Cuts (ML), pp. 351–362.
ML-1991-SuttonM #learning: Learning Polynomial Functions by Feature Construction (RSS, CJM), pp. 208–212.
DAC-1991-SiglDJ #linear #question: Analytical Placement: A Linear or a Quadratic Objective Function? (GS, KD, FMJ), pp. 427–432.
STOC-1991-BarnesR #algorithm #sublinear #using: Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (GB, WLR), pp. 43–53.
STOC-1991-Ko #equation: Integral Equations, Systems of Quadratic Equations, and Exponential-Time Completeness (KIK), pp. 10–20.
PODS-1990-Chomicki #database #deduction #query: Polynomial Time Query Processing in Temporal Deductive Databases (JC), pp. 379–391.
PODS-1990-Saraiya #database #deduction #program transformation: Polynomial-Time Program Transformations in Deductive Databases (YPS), pp. 132–144.
SIGMOD-1990-Wang #design #performance #towards: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation (KW), pp. 74–83.
ICALP-1990-JerrumS #algorithm #approximate: Polynomial-Time Approximation Algorithms for Ising Model (MJ, AS), pp. 462–475.
GG-1990-Lichtblau: Recognizing Rooted Context-free Flowgraph Languages in Polynomial Time (UL), pp. 538–548.
GG-1990-Vogler #graph: Recognizing Edge Replacement Graph Languages in Cubic Time (WV), pp. 676–687.
DAC-1990-ChakradharAB #automation #generative #programming #testing #using: Automatic Test Generation Using Quadratic 0-1 Programming (STC, VDA, MLB), pp. 654–659.
STOC-1990-BorodinT #decidability #on the: On the Decidability of Sparse Univariate Polynomial Interpolation (AB, PT), pp. 535–545.
STOC-1990-OgiwaraW #bound #on the #set: On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets (MO, OW), pp. 457–467.
PODS-1989-Saraiya #recursion: Linearizing Nonlinear Recursions in Polynomial Time (YPS), pp. 182–189.
SIGIR-1989-Fuhr #retrieval: Optimum Polynomial Retrieval Functions (NF), pp. 69–76.
STOC-1989-CohenM #algorithm #detection #graph: Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (EC, NM), pp. 523–534.
STOC-1989-DyerFK #algorithm #approximate #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: On Search, Decision and the Efficiency of Polynomial-Time Algorithms (MRF, MAL), pp. 501–512.
STOC-1989-PittW #approximate #automaton #consistency #problem: The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial (LP, MKW), pp. 421–432.
STOC-1989-Vallee #integer #performance: Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues (BV), pp. 98–106.
CSL-1989-Ambos-SpiesY #recursion #set: Honest Polynomial-Time Degrees of Elementary Recursive Sets (KAS, DY), pp. 1–15.
SIGMOD-1988-LeuchnerMS #algorithm #dependence #functional #testing: A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies (JHL, LM, GS), pp. 218–224.
ICALP-1988-LingasS #algorithm #graph #morphism: A Polynomial-Time Algorithm for Subgraph Isomorphism of Two-Connected Series-Parallel Graphs (AL, MMS), pp. 394–409.
ICALP-1988-TangB #reduction #set: Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets (ST, RVB), pp. 591–599.
DAC-1988-PillageR #metric: A Quadratic Metric with a Simple Solution Scheme for Initial Placement (LTP, RAR), pp. 324–329.
STOC-1988-Istrail #sequence #traversal: Polynomial Universal Traversing Sequences for Cycles Are Constructible (SI), pp. 491–503.
STOC-1988-KosarajuS #detection #graph: Detecting Cycles in Dynamic Graphs in Polynomial Time (SRK, GFS), pp. 398–406.
CADE-1988-GallierNPRS #canonical #equation #finite #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: Completeness with Respect to Interpretations in Deterministic and Nondeterministic Polynomial Time (ED), pp. 52–62.
STOC-1987-AdlemanH #random: Recognizing Primes in Random Polynomial Time (LMA, MDAH), pp. 462–469.
CSL-1987-Ambos-SpiesFH: Diagonalizing over Deterministic Polynomial Time (KAS, HF, HH), pp. 1–16.
CSL-1987-LenzW #complexity: The Conjunctive Complexity of Quadratic Boolean Functions (KL, IW), pp. 138–150.
CSL-1987-Spreen #nondeterminism #on the: On Functions Computable in Nondeterministic Polynomial Time: Some Characterizations (DS), pp. 289–303.
ICALP-1986-AverbuchWG #algorithm #classification: 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.
STOC-1986-Ben-OrFKT #algorithm #parallel #performance: A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots (MBO, EF, DK, PT), pp. 340–349.
STOC-1986-Cai #probability #random: With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy (JyC), pp. 21–29.
STOC-1986-KapoorV #algorithm #multi #performance #programming: Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows (SK, PMV), pp. 147–159.
STOC-1986-KoLD #morphism: A Note on One-Way Functions and Polynomial-Time Isomorphisms (KIK, TJL, DZD), pp. 295–303.
CADE-1986-CherifaL #implementation #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.
ICALP-1985-OrponenRS #complexity: Polynomial Levelability and Maximal Complexity Cores (PO, DAR, US), pp. 435–444.
DAC-1985-Blanks #using: Near-optimal placement using a quadratic objective function (JPB), pp. 609–615.
STOC-1985-Buss #bound: The Polynomial Hierarchy and Fragments of Bounded Arithmetic (SRB), pp. 285–290.
STOC-1985-FriedlR #algebra #problem: Polynomial Time Solutions of Some Problems in Computational Algebra (KF, LR), pp. 153–162.
STOC-1984-AdlerM #algorithm #bound: A Simplex Algorithm Whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension (IA, NM), pp. 312–323.
STOC-1984-Gonnet #equivalence #random: Determining Equivalence of Expressions in Random Polynomial Time (GHG), pp. 334–341.
STOC-1984-KannanLL #algebra: Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers (RK, AKL, LL), pp. 191–200.
STOC-1984-Karmarkar #algorithm #linear #programming: A New Polynomial-Time Algorithm for Linear Programming (NK), pp. 302–311.
STOC-1984-Maass #bound #nondeterminism #turing machine: Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (WM), pp. 401–408.
STOC-1984-OngSS #equation #performance: An Efficient Signature Scheme Based on Quadratic Equations (HO, CPS, AS), pp. 208–216.
ICALP-1983-GathenK #finite #multi: Polynomial-Time Factorization of Multivariate Polynomials over Finite Fields (JvzG, EK), pp. 250–263.
STOC-1983-Heide #algorithm #linear #problem: A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem (FMadH), pp. 70–79.
STOC-1983-KanellakisCV #dependence #problem: Unary Inclusion Dependencies have Polynomial Time Inference Problems (PCK, SSC, MYV), pp. 264–277.
STOC-1983-LandauM: Solvability by Radicals is in Polynomial Time (SL, GLM), pp. 140–151.
STOC-1983-Young #set: Some Structural Properties of Polynomial Reducibilities and Sets in NP (PY), pp. 392–401.
ICALP-1982-FlajoletS #branch #process: A Branching Process Arising in Dynamic Hashing, Trie Searching and Polynomial Factorization (PF, JMS), pp. 239–251.
STOC-1982-DolevS #algorithm #multi: Polynomial Algorithms for Multiple Processor Agreement (DD, HRS), pp. 401–407.
STOC-1982-Immerman #query #relational: Relational Queries Computable in Polynomial Time (NI), pp. 147–152.
STOC-1982-Kaltofen #multi #reduction: A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization (EK), pp. 261–266.
ICALP-1981-HeintzS #decidability #random: Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables (JH, MS), pp. 16–28.
POPL-1981-Rosen #linear: Linear Cost is Sometimes Quadratic (BKR), pp. 117–124.
STOC-1981-BertoniMS #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 #source code: Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (DJ, PY), pp. 55–61.
STOC-1980-FilottiM #algorithm #graph #morphism: A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (ISF, JNM), pp. 236–243.
STOC-1980-Tompa80a #algorithm #implementation #sublinear #transitive: Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations (MT), pp. 333–338.
ICALP-1979-Selman #behaviour #set: P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP (ALS), pp. 546–555.
POPL-1979-LiuF #pattern matching #string: String Pattern Matching in Polynomial Time (KCL, ACF), pp. 222–225.
STOC-1979-Cook: Deterministic CFL’s Are Accepted Simultaneously in Polynomial Time and Log Squared Space (SAC), pp. 338–345.
STOC-1979-GilbertLT #problem: The Pebbling Problem is Complete in Polynomial Space (JRG, TL, RET), pp. 237–248.
STOC-1979-Long #on the: On γ-Reducibility versus Polynomial Time Many-One Reducibility (TJL), pp. 278–287.
STOC-1978-Filotti #algorithm #graph #performance: An Efficient Algorithm for Determining Whether a Cubic Graph is Toroidal (ISF), pp. 133–142.
STOC-1978-Wegener #complexity: Switching Functions Whose Monotone Complexity Is Nearly Quadratic (IW), pp. 143–149.
ICALP-1977-PazM #approximate #nondeterminism #optimisation #problem: Non-Deterministic Polynomial Optimization Problems and Their Approximation (AP, SM), pp. 370–379.
STOC-1977-SimonG: Polynomial Reducibilities and Upward Diagonalizations (IS, JG), pp. 186–194.
STOC-1976-GrahamHR #context-free grammar #on the #recognition: On Line Context Free Language Recognition in Less than Cubic Time (SLG, MAH, WLR), pp. 112–120.
STOC-1976-MandersA #problem: NP-Complete Decision Problems for Quadratic Polynomials (KLM, LMA), pp. 23–29.
STOC-1975-EvenT #combinator #problem: a Combinatorial Problem which is Complete in Polynomial Space (SE, RET), pp. 66–71.
STOC-1975-Wotschke #problem #recognition: Degree-Languages, Polynomial Time Recognition, and the LBA Problem (DW), pp. 145–152.
STOC-1975-Yao #on the: On Computing the Minima of Quadratic Forms (ACCY), pp. 23–26.
STOC-1974-CookS #requirements: Storage Requirements for Deterministic Polynomial Time Recognizable Languages (SAC, RS), pp. 33–39.
STOC-1974-JonesL #problem: Complete Problems for Deterministic Polynomial Time (NDJ, WTL), pp. 40–46.
STOC-1974-LadnerLS: Comparisons of Polynomial-Time Reducibilities (REL, NAL, ALS), pp. 110–121.
STOC-1974-Mehlhorn #recursion: Polynomial and Abstract Subrecursive Classes (KM), pp. 96–109.
SOSP-1973-Ullman #problem #scheduling: Polynomial Complete Scheduling Problems (JDU), pp. 96–101.
STOC-1973-Greibach #context-free grammar: Jump PDA’s, Deterministic Context-Free Languages Principal AFDLs and Polynomial Time Recognition-Extended Abstract (SAG), pp. 20–28.
STOC-1973-Ladner: Polynomial Time Reducibility (REL), pp. 122–129.
STOC-1972-Fiduccia #algorithm #evaluation #fourier #performance #revisited: Polynomial Evaluation via the Division Algorithm: The Fast Fourier Transform Revisited (CMF), pp. 88–93.