BibSLEIGH — complexity tag

complexity

complexity

Tag #complexity

1390 papers:

POPL-2020-FeldmanISS #invariant: Complexity and information in invariant inference (YMYF, NI, MS, SS), p. 29.
CSL-2020-Buss0K #branch #nondeterminism #proving #source code: Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs (SB, AD0, AK), p. 17.
CSL-2020-SchmidtSVZK #algorithm: Dynamic Complexity Meets Parameterised Algorithms (JS, TS, NV, TZ, IK), p. 17.
CSL-2020-VortmeierZ #query: Dynamic Complexity of Parity Exists Queries (NV, TZ), p. 16.
EDM-2019-BahargamLT #algorithm #clustering #problem: The Guided Team-Partitioning Problem: Definition, Complexity, and Algorithm (SB, TL, ET).
EDM-2019-Venantd #concept #graph #predict #semantics #towards: Towards the Prediction of Semantic Complexity Based on Concept Graphs (RV, Md).
ICSME-2019-Alqadi #fault #probability: The Relationship Between Cognitive Complexity and the Probability of Defects (BSA), pp. 600–604.
CIAA-2019-Hospodar: Descriptional Complexity of Power and Positive Closure on Convex Languages (MH), pp. 158–170.
DLT-2019-Gao #bound #education #pattern matching: The Teaching Complexity of Erasing Pattern Languages with Bounded Variable Frequency (ZG), pp. 154–167.
DLT-2019-Lejeune0R #word: Computing the k-binomial Complexity of the Thue-Morse Word (ML, JL0, MR), pp. 278–291.
CoG-2019-Lanzi #using: Evaluating the Complexity of Players' Strategies using MCTS Iterations (PLL), pp. 1–8.
ICML-2019-0001MZLK #adaptation #approximate #memory management #streaming: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity (EK0, MM, MZ, SL, AK), pp. 3311–3320.
ICML-2019-0002WF #clustering #kernel #query: Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering (TY0, DPW, MF), pp. 7055–7063.
ICML-2019-AcharyaS #communication #estimation: Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (JA, ZS), pp. 51–60.
ICML-2019-FahrbachMZ #adaptation #query: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (MF, VSM, MZ), pp. 1833–1842.
ICML-2019-HaninR #linear #network: Complexity of Linear Regions in Deep Networks (BH, DR), pp. 2596–2604.
ICML-2019-KroshninTDDGU #approximate #on the: On the Complexity of Approximating Wasserstein Barycenters (AK, NT, DD, PED, AG, CAU), pp. 3530–3540.
ICML-2019-NdiayeLFST #grid: Safe Grid Search with Optimal Complexity (EN, TL, OF, JS, IT), pp. 4771–4780.
ICML-2019-RouletDSH #algorithm: Iterative Linearized Control: Stable Algorithms and Complexity Guarantees (VR, DD, SSS, ZH), pp. 5518–5527.
ICML-2019-SimonovFGP: Refined Complexity of PCA with Outliers (KS, FVF, PAG, FP), pp. 5818–5826.
ICML-2019-YinRB #robust: Rademacher Complexity for Adversarially Robust Generalization (DY, KR, PLB), pp. 7085–7094.
ICML-2019-YuJ #communication #on the #optimisation #parallel #probability: On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization (HY, RJ), pp. 7174–7183.
KDD-2019-Bradley #challenge #set: Addressing Challenges in Data Science: Scale, Skill Sets and Complexity (JB), p. 3163.
OOPSLA-2019-BiswasE #consistency #on the #transaction: On the complexity of checking transactional consistency (RB, CE), p. 28.
ESEC-FSE-2019-AwadhutkarSHK #algorithm #detection #named: DISCOVER: detecting algorithmic complexity vulnerabilities (PA, GRS, BH, SK), pp. 1129–1133.
ASPLOS-2019-GanZHCHPD #big data #debugging #named #performance: Seer: Leveraging Big Data to Navigate the Complexity of Performance Debugging in Cloud Microservices (YG0, YZ, KH, DC, YH, MP, CD), pp. 19–33.
CAV-2019-BiswasEE #consistency #data type #on the: On the Complexity of Checking Consistency for Replicated Data Types (RB, ME, CE), pp. 324–343.
ICTSS-2019-YevtushenkoKK #adaptation #nondeterminism #sequence: Evaluating the Complexity of Deriving Adaptive Homing, Synchronizing and Distinguishing Sequences for Nondeterministic FSMs (NY, VVK, NK), pp. 86–103.
CIAA-2018-0002J: The Exact Complexity of Star-Complement-Star (JJ0, GJ), pp. 223–235.
CIAA-2018-BrzozowskiKLS #assembly: State Complexity of Overlap Assembly (JAB, LK, BL, MS), pp. 109–120.
CIAA-2018-Davies #automaton #finite: State Complexity of Reversals of Deterministic Finite Automata with Output (SD), pp. 133–145.
CIAA-2018-MoldagaliyevS0 #on the: On the Values for Factor Complexity (BM, LS, FS0), pp. 274–285.
CIAA-2018-SinghK #automaton #on the: On Syntactic Complexity of Circular Semi-flower Automata (SNS, KVK), pp. 312–323.
CIAA-2018-Sinnamon #regular expression: Complexity of Proper Suffix-Convex Regular Languages (CS), pp. 324–338.
DLT-2018-0001JJ #automaton #finite #problem #self #verification: Computational Complexity of Decision Problems on Self-verifying Finite Automata (MH0, SJ, JJJ), pp. 404–415.
DLT-2018-Davies #approach #formal method: A General Approach to State Complexity of Operations: Formalization and Limitations (SD), pp. 256–268.
DLT-2018-EberhardEH #problem: Complexity of Decision Problems on Totally Rigid Acyclic Tree Grammars (SE, GE, SH), pp. 291–303.
DLT-2018-JiraskovaO #automaton #bound #towards: Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata (GJ, AO), pp. 441–452.
ICFP-2018-Das0P #analysis #parallel: Parallel complexity analysis with temporal session types (AD, JH0, FP), p. 30.
ICML-2018-DvurechenskyGK #algorithm: Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm (PED, AG, AK), pp. 1366–1375.
ICPR-2018-GarciaLSH #classification #metric #recommendation #using: Classifier Recommendation Using Data Complexity Measures (LPFG, ACL, MCPdS, TKH), pp. 874–879.
ESEC-FSE-2018-WeiCFFD #fuzzing #named: Singularity: pattern fuzzing for worst case complexity (JW, JC, YF, KF, ID), pp. 213–223.
CASE-2018-LongoFMMS #approach #big data #monitoring: Big Data for advanced monitoring system: an approach to manage system complexity (CSL, CF, FM, LM, MS), pp. 341–346.
ESOP-2018-GueneauCP #deduction #formal method #verification: A Fistful of Dollars: Formalizing Asymptotic Complexity Claims via Deductive Program Verification (AG, AC, FP), pp. 533–560.
ESOP-2018-MertenBS #algorithm #distributed #game studies #learning: Verified Learning Without Regret - From Algorithmic Game Theory to Distributed Systems with Mechanized Complexity Guarantees (SM, AB, GS0), pp. 561–588.
CAV-2018-RobereKG #proving #smt: The Proof Complexity of SMT Solvers (RR, AK, VG), pp. 275–293.
CSL-2018-BaillotG #linear #logic: Combining Linear Logic and Size Types for Implicit Complexity (PB, AG), p. 21.
CSL-2018-Luck #canonical #logic #modelling: Canonical Models and the Complexity of Modal Team Logic (ML), p. 23.
CSL-2018-ZaidKL #automation: Climbing up the Elementary Complexity Classes with Theories of Automatic Structures (FAZ, DK, PL), p. 16.
IJCAR-2018-BodirskyG #constraints #problem: Complexity of Combinations of Qualitative Constraint Satisfaction Problems (MB, JG), pp. 263–278.
IJCAR-2018-ZhanH #imperative #source code #verification: Verifying Asymptotic Time Complexity of Imperative Programs in Isabelle (BZ, MPLH), pp. 532–548.
VMCAI-2018-FiedorHRSVZ: From Shapes to Amortized Complexity (TF, LH, AR, MS, TV, FZ), pp. 205–225.
ICPC-2017-AjamiWF #question #syntax #what: Syntax, predicates, idioms: what really affects code complexity? (SA, YW, DGF), pp. 66–76.
AFL-2017-BeierHK #linear #on the #set: On the Descriptional Complexity of Operations on Semilinear Sets (SB, MH, MK), pp. 41–55.
AFL-2017-MaraisZ #automaton #difference #self #symmetry #verification: Descriptional Complexity of Non-Unary Self-Verifying Symmetric Difference Automata (LM, LvZ), pp. 157–169.
CIAA-2017-AcetoAFIK #monitoring #on the: On the Complexity of Determinizing Monitors (LA, AA, AF, AI, SÖK), pp. 1–13.
CIAA-2017-BrzozowskiS #regular expression: Complexity of Proper Prefix-Convex Regular Languages (JAB, CS), pp. 52–63.
CIAA-2017-FerensS #regular expression: Complexity of Bifix-Free Regular Languages (RF, MS), pp. 76–88.
CIAA-2017-HospodarJM #nondeterminism: Nondeterministic Complexity of Operations on Free and Convex Languages (MH, GJ, PM), pp. 138–150.
CIAA-2017-SzykulaW: Syntactic Complexity of Bifix-Free Languages (MS, JW), pp. 201–212.
DLT-2017-Beier0 #on the #proving #regular expression: On Regular Expression Proof Complexity (SB, MH0), pp. 83–95.
DLT-2017-Beier0K #automaton #decidability #finite: Operational State Complexity and Decidability of Jumping Finite Automata (SB, MH0, MK), pp. 96–108.
DLT-2017-HospodarJM #on the: On the Descriptive Complexity of Σ∗L (MH, GJ, PM), pp. 222–234.
DLT-2017-LodayaS #first-order #logic #quantifier: Two-Variable First Order Logic with Counting Quantifiers: Complexity Results (KL, AVS), pp. 260–271.
DLT-2017-RubtsovV #automaton #on the #set: On Computational Complexity of Set Automata (AAR, MNV), pp. 332–344.
DLT-2017-Skrzypczak #decidability #logic: Connecting Decidability and Complexity for MSO Logic (MS), pp. 75–79.
DLT-2017-Yamakami #automaton #bound #probability: One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity - (Preliminary Report) (TY), pp. 353–364.
FSCD-2017-DudenhefnerR: The Complexity of Principal Inhabitation (AD, JR), p. 14.
IFM-2017-FrohnG #analysis #java: Complexity Analysis for Java with AProVE (FF, JG), pp. 85–101.
ICFP-2017-AvanziniL #analysis #automation #type inference: Automating sized-type inference for complexity analysis (MA, UDL), p. 29.
AIIDE-2017-StephensonRG #game studies: The Computational Complexity of Angry Birds and Similar Physics-Simulation Games (MS, JR, XG), pp. 241–247.
ICML-2017-ArjevaniS #higher-order #problem: Oracle Complexity of Second-Order Methods for Finite-Sum Problems (YA, OS), pp. 205–213.
ICML-2017-HeckelR #collaboration #online: The Sample Complexity of Online One-Class Collaborative Filtering (RH, KR), pp. 1452–1460.
ICML-2017-LiuLNT #algorithm: Algorithmic Stability and Hypothesis Complexity (TL, GL, GN, DT), pp. 2159–2167.
ICML-2017-ShenL #on the: On the Iteration Complexity of Support Recovery via Hard Thresholding Pursuit (JS0, PL0), pp. 3115–3124.
OOPSLA-2017-WangWC #analysis #functional #invariant #named: TiML: a functional language for practical complexity analysis with invariants (PW0, DW, AC), p. 26.
POPL-2017-SrikanthSH #theorem #using #verification: Complexity verification using guided theorem enumeration (AS, BS, WRH), pp. 639–652.
PPDP-2017-AccattoliB #automaton: Environments and the complexity of abstract machines (BA, BB), pp. 4–16.
ASE-2017-KavalerSHAF #git: Perceived language complexity in GitHub issue discussions and their effect on issue resolution (DK, SS, VH, RA, VF), pp. 72–83.
CASE-2017-LiXZ #analysis #learning: Complexity analysis of reinforcement learning and its application to robotics (BL, LX, QZ), pp. 1425–1426.
ESOP-2017-KopS #higher-order #nondeterminism #power of #programming #using: The Power of Non-determinism in Higher-Order Implicit Complexity - Characterising Complexity Classes Using Non-deterministic Cons-Free Programming (CK, JGS), pp. 668–695.
CSL-2017-VerbitskyZ #first-order #morphism #on the: On the First-Order Complexity of Induced Subgraph Isomorphism (OV, MZ), p. 16.
ICST-2017-LuckowKP #analysis #using: Symbolic Complexity Analysis Using Context-Preserving Histories (KSL, RK, CSP), pp. 58–68.
ICSME-2016-LudemannASV #comprehension #variability: Understanding Variable Code: Reducing the Complexity by Integrating Variability Information (DL, NA, KS, CV), pp. 312–322.
SCAM-2016-HollandSAK #algorithm #detection #dynamic analysis #tool support: Statically-Informed Dynamic Analysis Tools to Detect Algorithmic Complexity Vulnerabilities (BH, GRS, PA, SK), pp. 79–84.
CIAA-2016-HospodarJM #nondeterminism: Nondeterministic Complexity of Operations on Closed and Ideal Languages (MH, GJ, PM), pp. 125–137.
CIAA-2016-Prusa #2d #set: Complexity of Sets of Two-Dimensional Patterns (DP), pp. 236–247.
CIAA-2016-SekiW #self: The Complexity of Fixed-Height Patterned Tile Self-assembly (SS, AW), pp. 248–259.
DLT-2016-CadilhacKL #approach: A Language-Theoretical Approach to Descriptive Complexity (MC, AK, KJL), pp. 64–76.
FSCD-2016-AvanziniM #graph grammar: Complexity of Acyclic Term Graph Rewriting (MA, GM), p. 18.
FSCD-2016-KopS #higher-order: Complexity Hierarchies and Higher-Order Cons-Free Rewriting (CK, JGS), p. 18.
ICFP-2016-CicekP0 #control flow #incremental #type system: A type theory for incremental computational complexity with control flow changes (EÇ, ZP, DG0), pp. 132–145.
ICML-2016-ArjevaniS #algorithm #first-order #on the #optimisation: On the Iteration Complexity of Oblivious First-Order Optimization Algorithms (YA, OS), pp. 908–916.
ICML-2016-SuhZA #classification: The Label Complexity of Mixed-Initiative Classifier Training (JS, XZ0, SA), pp. 2800–2809.
ICPR-2016-LittwinW #multi #network: Complexity of multiverse networks and their multilayer generalization (EL, LW), pp. 372–377.
ICPR-2016-Liu0 #online: One-pass online SVM with extremely small space complexity (YL, JX0), pp. 3482–3487.
ICPR-2016-NilssonO #classification #pattern matching #pattern recognition #recognition: Estimates of Classification Complexity for Myoelectric Pattern Recognition (NN, MOC), pp. 2682–2687.
PLDI-2016-0001HM #on the #parsing #performance: On the complexity and performance of parsing with derivatives (MDA0, CH, MM), pp. 224–236.
POPL-2016-GimenezM #interactive: The complexity of interaction (SG, GM), pp. 243–255.
ASE-2016-MeinickeWKTS #configuration management #interactive #on the: On essential configuration complexity: measuring interactions in highly-configurable systems (JM, CPW, CK, TT, GS), pp. 483–494.
ICSE-2016-MoCKXF #architecture #maintenance #metric: Decoupling level: a new metric for architectural maintenance complexity (RM, YC, RK, LX0, QF), pp. 499–510.
CSL-2016-0001HKV: Descriptive Complexity of #AC0 Functions (AD0, AH, JK, HV), p. 16.
CSL-2016-GanardiGL #bisimulation #finite #on the #parallel: On the Parallel Complexity of Bisimulation on Finite Systems (MG, SG, ML), p. 17.
CSL-2016-KarandikarS #logic: The Height of Piecewise-Testable Languages with Applications in Logical Complexity (PK, PS), p. 22.
IJCAR-2016-Boudou #composition #logic #parallel: Complexity Optimal Decision Procedure for a Propositional Dynamic Logic with Parallel Composition (JB), pp. 373–388.
PODS-2015-FaginKK: Dichotomies in the Complexity of Preferred Repairs (RF, BK, PGK), pp. 3–15.
PODS-2015-GuchtWWZ #communication #distributed #matrix #multi: The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication (DVG, RW, DPW, QZ), pp. 199–212.
PODS-2015-Kapralov #nearest neighbour #query #trade-off: Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search (MK), pp. 329–342.
PODS-2015-KoutrisW #consistency #constraints #query #self: The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints (PK, JW), pp. 17–29.
CIAA-J-2013-BalkanskiBKW15 #on the #word: On the state complexity of partial word DFAs (EB, FBS, MK, BJW), pp. 2–12.
CIAA-2015-AdigaKMRRS: Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems (AA, CJK, MVM, SSR, DJR, RES), pp. 21–34.
CIAA-2015-FernauPS #automaton #finite: Jumping Finite Automata: Characterizations and Complexity (HF, MP, MLS), pp. 89–101.
CIAA-2015-NgRS #distance: State Complexity of Prefix Distance (TN, DR, KS), pp. 238–249.
DLT-2015-AvgustinovichFP #infinity #permutation: Ergodic Infinite Permutations of Minimal Complexity (SVA, AEF, SP), pp. 71–84.
DLT-2015-BrandlS #analysis #automaton #finite #monad: Complexity Analysis: Transformation Monoids of Finite Automata (CB, HUS), pp. 143–154.
DLT-2015-BrlekLP: Palindromic Complexity of Trees (SB, NL, XP), pp. 155–166.
DLT-2015-MasopustT #automaton #on the #testing: On the Complexity of k-Piecewise Testability and the Depth of Automata (TM, MT), pp. 364–376.
DLT-2015-NgRS #approximate #pattern matching: State Complexity of Neighbourhoods and Approximate Pattern Matching (TN, DR, KS), pp. 389–400.
DLT-2015-Yamakami #bound #quantum: Complexity Bounds of Constant-Space Quantum Computation — (TY), pp. 426–438.
ICALP-v1-2015-AgrawalIKP #encoding #perspective #random #statistics: Statistical Randomized Encodings: A Complexity Theoretic View (SA, YI, DK, APC), pp. 1–13.
ICALP-v1-2015-BurtonMS #algorithm #invariant: Algorithms and Complexity for Turaev-Viro Invariants (BAB, CM, JS), pp. 281–293.
ICALP-v1-2015-Curticapean #framework: Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity (RC), pp. 380–392.
ICALP-v1-2015-FontesJKLLR #communication: Relative Discrepancy Does not Separate Information and Communication Complexity (LF, RJ, IK, SL, ML, JR), pp. 506–516.
ICALP-v1-2015-GiannopoulouJLS #kernel: Uniform Kernelization Complexity of Hitting Forbidden Minors (ACG, BMPJ, DL, SS), pp. 629–641.
ICALP-v1-2015-KaniewskiLW #query: Query Complexity in Expectation (JK, TL, RdW), pp. 761–772.
ICALP-v1-2015-KannanM0 #graph #query: Near-Linear Query Complexity for Graph Inference (SK, CM, HZ), pp. 773–784.
ICALP-v1-2015-MolinaroWY: Amplification of One-Way Information Complexity via Codes and Noise Sensitivity (MM, DPW, GY), pp. 960–972.
ICALP-v2-2015-Chatterjee0V #component #probability #synthesis: The Complexity of Synthesis from Probabilistic Components (KC, LD, MYV), pp. 108–120.
ICALP-v2-2015-SwernofskyW #on the: On the Complexity of Intersecting Regular, Context-Free, and Tree Languages (JS, MW), pp. 414–426.
LATA-2015-AllenderM: Complexity of Regular Functions (EA, IM), pp. 449–460.
LATA-2015-BachmeierLS #automaton #finite: Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity (GB, ML, MS), pp. 473–485.
LATA-2015-BresolinMMSS #logic #on the: On the Complexity of Fragments of the Modal Logic of Allen’s Relations over Dense Structures (DB, DDM, AM, PS, GS), pp. 511–523.
LATA-2015-LuckMS #theorem: Parameterized Complexity of CTL — A Generalization of Courcelle’s Theorem (ML, AM, IS), pp. 549–560.
LATA-2015-MauriLMPZ #overview: Complexity Classes for Membrane Systems: A Survey (GM, AL, LM, AEP, CZ), pp. 56–69.
LATA-2015-VorelR #word: Complexity of Road Coloring with Prescribed Reset Words (VV, AR), pp. 161–172.
RTA-2015-AvanziniST #certification #proving #using: Certification of Complexity Proofs using CeTA (MA, CS, RT), pp. 23–39.
RTA-2015-FrohnGHAS #bound #runtime: Inferring Lower Bounds for Runtime Complexity (FF, JG, JH, CA, TS), pp. 334–349.
RTA-2015-KopMS: Conditional Complexity (CK, AM, TS), pp. 223–240.
ICFP-2015-AvanziniLM #first-order #functional #higher-order #source code: Analysing the complexity of functional programs: higher-order meets first-order (MA, UDL, GM), pp. 152–164.
FDG-2015-KapadiaZFMS #artificial reality #authoring #interactive: Evaluating the Authoring Complexity of Interactive Narratives for Augmented Reality Applications (MK, FZ, JF, MM, RWS).
HCI-DE-2015-Teixeira-FariaI #abstraction #component #interactive #visual notation: Reduce Complexity by Increasing Abstraction in Interactive Visual Components (PMTF, JRI), pp. 426–437.
HCI-IT-2015-BakaevA #human-computer #optimisation #user interface: Defining and Optimizing User Interfaces Information Complexity for AI Methods Application in HCI (MB, TA), pp. 397–405.
HIMI-IKC-2015-RobertsACC #communication: A Method for Calculating Air Traffic Controller Communication Complexity (ZR, BA, JC, DC), pp. 25–32.
LCT-2015-ValdezBGSZ #visualisation #what: What Do My Colleagues Know? Dealing with Cognitive Complexity in Organizations Through Visualizations (ACV, SB, CG, US, MZ), pp. 449–459.
ICEIS-v1-2015-Mocker #how: Complexity in the Digital Age — How can IT Help, not Hurt (MM), p. IX.
ICEIS-v2-2015-ThommazoCHGPBF #dependence #requirements #testing #using: Using the Dependence Level Among Requirements to Priorize the Regression Testing Set and Characterize the Complexity of Requirements Change (ADT, KC, EMH, GG, JP, AB, SF), pp. 231–241.
ICML-2015-ZhuG #robust #towards: Towards a Lower Sample Complexity for Robust One-bit Compressed Sensing (RZ, QG), pp. 739–747.
KDD-2015-LanH #learning #multi: Reducing the Unlabeled Sample Complexity of Semi-Supervised Multi-View Learning (CL, JH), pp. 627–634.
SEKE-2015-YungLC #black box: An Average Case Time Complexity Estimator for Black-box Functions (DY, BL, SKC), pp. 567–570.
SIGIR-2015-CapraACV #difference #using: Differences in the Use of Search Assistance for Tasks of Varying Complexity (RC, JA, AC, EV), pp. 23–32.
MoDELS-2015-KulkarniBCB #towards: Toward overcoming accidental complexity in organisational decision-making (VK, SB, TC, BSB), pp. 368–377.
Onward-2015-HolderTG #assessment #music #named: Musiplectics: computational assessment of the complexity of music scores (EH, ET, AG), pp. 107–120.
POPL-2015-ElangoRPRS #data access #on the #source code: On Characterizing the Data Access Complexity of Programs (VE, FR, LNP, JR, PS), pp. 567–580.
ESEC-FSE-2015-BangAB #automation #source code: Automatically computing path complexity of programs (LB, AA, TB), pp. 61–72.
SAC-2015-OliveiraQMM #community #detection #using: Community detection, with lower time complexity, using coupled Kuramoto oscillators (JEMdO, MGQ, MDNM, EENM), pp. 1160–1166.
CASE-2015-WuJG #optimisation: Local and global event-based optimization: Performace and complexity (ZW, QSJ, XG), pp. 1375–1380.
DAC-2015-SuC: Nanowire-aware routing considering high cut mask complexity (YHS, YWC), p. 6.
ESOP-2015-CicekGA #incremental #refinement: Refinement Types for Incremental Computational Complexity (EÇ, DG, UAA), pp. 406–431.
STOC-2015-AbrahamD #polynomial: Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity (IA, DD), pp. 605–614.
STOC-2015-AlwenS #graph #parallel: High Parallel Complexity Graphs and Memory-Hard Functions (JA, VS), pp. 595–603.
STOC-2015-ChenDO #game studies #nash #on the: On the Complexity of Nash Equilibria in Anonymous Games (XC, DD, AO), pp. 381–390.
STOC-2015-FearnleyS: The Complexity of the Simplex Method (JF, RS), pp. 201–208.
STOC-2015-FeldmanPV #on the #problem #random #satisfiability: On the Complexity of Random Satisfiability Problems with Planted Solutions (VF, WP, SV), pp. 77–86.
STOC-2015-GowersV #communication: The communication complexity of interleaved group products (TG, EV), pp. 351–360.
STOC-2015-Touchette #quantum: Quantum Information Complexity (DT), pp. 317–326.
CAV-2015-Ben-AmramG #ranking: Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions (AMBA, SG), pp. 304–321.
ICLP-J-2015-AlvianoL #compilation #programming #set: Complexity and compilation of GZ-aggregates in answer set programming (MA, NL), pp. 574–587.
ICTSS-2015-SchneiderWH #metric #testing: A Negative Input Space Complexity Metric as Selection Criterion for Fuzz Testing (MAS, MFW, AH0), pp. 257–262.
LICS-2015-BaazLR #proving: A Note on the Complexity of Classical and Intuitionistic Proofs (MB, AL, GR), pp. 657–666.
LICS-2015-BenediktCCB #bound #logic: The Complexity of Boundedness for Guarded Logics (MB, BtC, TC, MVB), pp. 293–304.
LICS-2015-BienvenuKP #owl #query: Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results (MB, SK, VVP), pp. 317–328.
LICS-2015-BozzelliP #equilibrium #logic #on the: On the Complexity of Temporal Equilibrium Logic (LB, DP), pp. 645–656.
LICS-2015-CarvalhoMM #algebra: From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP (CC, FRM, BM), pp. 462–474.
LICS-2015-DalmauEHLR #problem: Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy (VD, LE, PH, BL, AR), pp. 487–498.
LICS-2015-HeijltjesH #bound #logic #petri net #proving: Complexity Bounds for Sum-Product Logic via Additive Proof Nets and Petri Nets (WH, DJDH), pp. 80–91.
LICS-2015-LechnerOW #linear #on the: On the Complexity of Linear Arithmetic with Divisibility (AL, JO, JW), pp. 667–676.
ECSA-2014-FreudenreichAFB #architecture #policy #using: Using Policies for Handling Complexity of Event-Driven Architectures (TF, SA, SF, APB), pp. 114–129.
PODS-2014-PaghS: The input/output complexity of triangle enumeration (RP, FS), pp. 224–233.
SIGMOD-2014-TangXS #performance: Influence maximization: near-optimal time complexity meets practical efficiency (YT, XX, YS), pp. 75–86.
SIGMOD-2014-ZhangDI #on the #optimisation #query: On complexity and optimization of expensive queries in complex event processing (HZ, YD, NI), pp. 217–228.
DLT-J-2013-IbarraR14: Some Decision Questions Concerning the Time Complexity of Language Acceptors (OHI, BR), pp. 1127–1140.
AFL-2014-GruberH #automaton #finite #regular expression #summary: From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity (HG, MH), pp. 25–48.
AFL-2014-Valdats #regular expression: Boolean Circuit Complexity of Regular Languages (MV), pp. 342–354.
DLT-2014-BrzozowskiS #bound: Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals (JAB, MS), pp. 13–24.
DLT-2014-FeliceN #algorithm #automaton #on the: On the Average Complexity of Brzozowski’s Algorithm for Deterministic Automata with a Small Number of Final States (SDF, CN), pp. 25–36.
DLT-2014-HanKS: State Complexity of Deletion (YSH, SKK, KS), pp. 37–48.
ICALP-v1-2014-AmbainisBGMSZ #metric: Tighter Relations between Sensitivity and Other Complexity Measures (AA, MB, YG, JM, XS, SZ), pp. 101–113.
ICALP-v1-2014-DattaHK #problem #reachability: Dynamic Complexity of Directed Reachability and Other Problems (SD, WH, RK), pp. 356–367.
ICALP-v1-2014-DregiL: Parameterized Complexity of Bandwidth on Trees (MSD, DL), pp. 405–416.
ICALP-v1-2014-IvanyosKQSS #constraints #fault #on the #problem: On the Complexity of Trial and Error for Constraint Satisfaction Problems (GI, RK, YQ, MS, AS), pp. 663–675.
ICALP-v1-2014-KhotTW #approximate: The Complexity of Somewhat Approximation Resistant Predicates (SK, MT, PW), pp. 689–700.
ICALP-v1-2014-WimmerWZ #matrix #query: Optimal Query Complexity for Estimating the Trace of a Matrix (KW, YW, PZ), pp. 1051–1062.
ICALP-v2-2014-BellBMR #symmetry: Symmetric Groups and Quotient Complexity of Boolean Operations (JB, JAB, NM, RR), pp. 1–12.
ICALP-v2-2014-BundalaO #on the: On the Complexity of Temporal-Logic Path Checking (DB, JO), pp. 86–97.
ICALP-v2-2014-ChatterjeeI #game studies: The Complexity of Ergodic Mean-payoff Games (KC, RIJ), pp. 122–133.
ICALP-v2-2014-KieferW #automaton #probability: Stability and Complexity of Minimising Probabilistic Automata (SK, BW), pp. 268–279.
LATA-2014-FormentiHKP: ω-rational Languages: High Complexity Classes vs. Borel Hierarchy (EF, MH, MK, JP), pp. 372–383.
LATA-2014-Prusa: Weight-Reducing Hennie Machines and Their Descriptional Complexity (DP), pp. 553–564.
LATA-2014-Vorel #automaton #problem #word: Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata (VV), pp. 576–587.
LATA-2014-ZhengGQ #automaton #finite #on the: On the State Complexity of Semi-quantum Finite Automata (SZ, JG, DQ), pp. 601–612.
RTA-TLCA-2014-HirokawaM #analysis #automation: Automated Complexity Analysis Based on Context-Sensitive Rewriting (NH, GM), pp. 257–271.
RTA-TLCA-2014-SternagelT #algebra #certification #formal method #proving #termination: Formalizing Monotone Algebras for Certification of Termination and Complexity Proofs (CS, RT), pp. 441–455.
HCI-AS-2014-TsengT #correlation #design #online #trust #visual notation: The Correlation between Visual Complexity and User Trust in On-line Shopping: Implications for Design (KTT, YCT), pp. 90–99.
ICEIS-v2-2014-Chung #profiling #realtime #towards: Towards Real-time Static and Dynamic Profiling of Organisational Complexity (KSKC), pp. 466–471.
CIKM-2014-ShaoKTG #case study #distance #navigation #network #query: Travel distance versus navigation complexity: a study on different spatial queries on road networks (JS, LK, ET, LG), pp. 1791–1794.
ICML-c2-2014-DaneshmandGSS #algorithm #network: Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm (HD, MGR, LS, BS), pp. 793–801.
ICPR-2014-BaiHRE #graph: Directed Depth-Based Complexity Traces of Hypergraphs from Directed Line Graphs (LB, ERH, PR, FE), pp. 3874–3879.
KDD-2014-LiARS #modelling #topic: Reducing the sampling complexity of topic models (AQL, AA, SR, AJS), pp. 891–900.
KR-2014-HaanS #problem #reasoning: The Parameterized Complexity of Reasoning Problems Beyond NP (RdH, SS).
KR-2014-StrassW #approximate #fixpoint #framework: Analyzing the Computational Complexity of Abstract Dialectical Frameworks via Approximation Fixpoint Theory (HS, JPW).
SEKE-2014-AlemerienM #named #user interface #visual notation: GUIEvaluator: A Metric-tool for Evaluating the Complexity of Graphical User Interfaces (KA, KM), pp. 13–18.
SAC-2014-PereiraS #deduction #source code: Complexity checking of ARM programs, by deduction (MP, SMdS), pp. 1309–1314.
ASPLOS-2014-DingZZES #compilation #runtime #scheduling: Finding the limit: examining the potential and complexity of compilation scheduling for JIT-based runtime systems (YD, MZ, ZZ, SE, XS), pp. 607–622.
CASE-2014-HerrNV #distributed #framework #scheduling: Prognostics-based scheduling in a distributed platform: Model, complexity and resolution (NH, JMN, CV), pp. 1054–1059.
DAC-2014-SchaffnerGSKB #approximate #linear #realtime #video: An Approximate Computing Technique for Reducing the Complexity of a Direct-Solver for Sparse Linear Systems in Real-Time Video Processing (MS, FKG, AS, HK, LB), p. 6.
DATE-2014-AksoyFM #constant #design #multi #optimisation: Optimization of design complexity in time-multiplexed constant multiplications (LA, PFF, JCM), pp. 1–4.
OSDI-2014-PillaiCAAAA #file system: All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications (TSP, VC, RA, SAK, ACAD, RHAD), pp. 433–448.
FoSSaCS-2014-Chatterjee0NV #game studies #probability: The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies (KC, LD, SN, MYV), pp. 242–257.
FoSSaCS-2014-Tsukada0 #call-by #model checking #source code: Complexity of Model-Checking Call-by-Value Programs (TT, NK), pp. 180–194.
STOC-2014-Babichenko #approximate #nash #query: Query complexity of approximate nash equilibria (YB), pp. 535–544.
STOC-2014-ColeR: The sample complexity of revenue maximization (RC, TR), pp. 243–252.
STOC-2014-DanielyLS #learning: From average case complexity to improper learning complexity (AD, NL, SSS), pp. 441–448.
STOC-2014-GavinskyMWW #approach #bound #composition #towards: Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture (DG, OM, OW, AW), pp. 213–222.
STOC-2014-Rothvoss #exponential: The matching polytope has exponential extension complexity (TR), pp. 263–272.
STOC-2014-Williams14a #performance: Faster all-pairs shortest paths via circuit complexity (RW), pp. 664–673.
TACAS-2014-BrockschmidtEFFG #analysis #integer #runtime #source code: Alternating Runtime and Size Complexity Analysis of Integer Programs (MB, FE, SF, CF, JG), pp. 140–155.
CAV-2014-SinnZV #bound #scalability #static analysis: A Simple and Scalable Static Analysis for Bound Analysis and Amortized Complexity Analysis (MS, FZ, HV), pp. 745–761.
IJCAR-2014-BeyersdorffC #proving #theorem proving: The Complexity of Theorem Proving in Circumscription and Minimal Entailment (OB, LC), pp. 403–417.
ISSTA-2014-BohmeR #fault #named: CoREBench: studying complexity of regression errors (MB, AR), pp. 105–115.
LICS-CSL-2014-BaierKKW #decidability #linear #logic #monitoring: Weight monitoring with linear temporal logic: complexity and decidability (CB, JK, SK, SW), p. 10.
LICS-CSL-2014-BrenguierRS #game studies: The complexity of admissibility in ω-regular games (RB, JFR, MS), p. 10.
LICS-CSL-2014-ChenM #classification #graph #query: One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries (HC, MM), p. 10.
LICS-CSL-2014-KlinLOT #constraints #problem #turing machine: Turing machines with atoms, constraint satisfaction problems, and descriptive complexity (BK, SL, JO, ST), p. 10.
SAT-2014-IstrateC #proving #theorem: Proof Complexity and the Kneser-Lovász Theorem (GI, AC), pp. 138–153.
SAT-2014-Nordstrom #overview #proving #satisfiability: A (Biased) Proof Complexity Survey for SAT Practitioners (JN), pp. 1–6.
VMCAI-2014-AcunaAMS #approach #heuristic #modelling #network: Modeling Parsimonious Putative Regulatory Networks: Complexity and Heuristic Approach (VA, AA, AM, AS), pp. 322–336.
HT-2013-BurelH #community #maturity #online: A question of complexity: measuring the maturity of online enquiry communities (GB, YH), pp. 1–10.
PODS-2013-ChenM #classification #query: The fine classification of conjunctive queries and parameterized logarithmic space complexity (HC, MM), pp. 309–320.
PODS-2013-KimelfeldK #mining: The complexity of mining maximal frequent subgraphs (BK, PGK), pp. 13–24.
VLDB-2013-DengF #on the #query: On the Complexity of Query Result Diversification (TD, WF), pp. 577–588.
VLDB-2013-KimelfeldVW #approximate #multi: Multi-Tuple Deletion Propagation: Approximations and Complexity (BK, JV, DPW), pp. 1558–1569.
VLDB-2013-SzlichtaGGZ #dependence #order: Expressiveness and Complexity of Order Dependencies (JS, PG, JG, CZ), pp. 1858–1869.
ITiCSE-2013-Trakhtenbrot #algorithm #analysis #concept #problem #student: Students misconceptions in analysis of algorithmic and computational complexity of problems (MT), pp. 353–354.
SCAM-2013-JbaraF #assessment #linux: Characterization and assessment of the linux configuration complexity (AJ, DGF), pp. 11–20.
WCRE-2013-SchoenmakersBNVS: Assessing the complexity of upgrading software modules (BS, NvdB, IN, BV, AS), pp. 433–440.
CIAA-J-2012-KutribO13 #automaton #on the: On the Descriptional Complexity of the Window Size for Deleting Restarting Automata (MK, FO), pp. 831–846.
DLT-J-2012-BrzozowskiT13 #regular expression: Complexity of atoms of Regular Languages (JAB, HT), pp. 1009–1028.
CIAA-2013-BrzozowskiL: Universal Witnesses for State Complexity of Basic Operations Combined with Reversal (JAB, DL), pp. 72–83.
CIAA-2013-MaiaMR #finite: Incomplete Transition Complexity of Basic Operations on Finite Languages (EM, NM, RR), pp. 349–356.
DLT-2013-Blanchet-SadriF #on the #word: On the Asymptotic Abelian Complexity of Morphic Words (FBS, NF), pp. 94–105.
DLT-2013-GocSS: Subword Complexity and k-Synchronization (DG, LS, JS), pp. 252–263.
DLT-2013-IbarraR: Some Decision Questions Concerning the Time Complexity of Language Acceptors (OHI, BR), pp. 264–276.
ICALP-v1-2013-AvisT #combinator #on the: On the Extension Complexity of Combinatorial Polytopes (DA, HRT), pp. 57–68.
ICALP-v1-2013-BohlerCKLPZ #diagrams #higher-order #on the: On the Complexity of Higher Order Abstract Voronoi Diagrams (CB, PC, RK, CHL, EP, MZ), pp. 208–219.
ICALP-v1-2013-GuoW #csp: The Complexity of Planar Boolean #CSP with Complex Weights (HG, TW), pp. 516–527.
ICALP-v1-2013-GurR #streaming: Arthur-Merlin Streaming Complexity (TG, RR), pp. 528–539.
ICALP-v1-2013-HirtR #on the: On the Complexity of Broadcast Setup (MH, PR), pp. 552–563.
ICALP-v1-2013-LauriaPRT #graph #proving: The Complexity of Proving That a Graph Is Ramsey (ML, PP, VR, NT), pp. 684–695.
ICALP-v1-2013-Leonardos #bound #random #recursion: An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority, (NL), pp. 696–708.
ICALP-v1-2013-Uppman: The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom (HU), pp. 804–815.
ICALP-v1-2013-Velner #game studies #infinity: The Complexity of Infinitely Repeated Alternating Move Games (YV), pp. 816–827.
ICALP-v2-2013-BecchettiBDKM #bound #convergence #proving: Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds (LB, VB, MD, AK, KM), pp. 472–483.
ICALP-v2-2013-BenaimBCKLMW #finite #logic: Complexity of Two-Variable Logic on Finite Trees (SB, MB, WC, EK, RL, FM, JW), pp. 74–88.
ICALP-v2-2013-DemriDS #on the #verification: On the Complexity of Verifying Regular Properties on Flat Counter Systems, (SD, AKD, AS), pp. 162–173.
ICALP-v2-2013-HartungNNS #analysis #graph: A Refined Complexity Analysis of Degree Anonymization in Graphs (SH, AN, RN, OS), pp. 594–606.
ICALP-v2-2013-LeivantM #evolution: Evolving Graph-Structures and Their Implicit Computational Complexity (DL, JYM), pp. 349–360.
ICALP-v2-2013-LipmaaT #online #similarity #sublinear #testing: Secure Equality and Greater-Than Tests with Sublinear Online Complexity (HL, TT), pp. 645–656.
LATA-2013-AlurKTY #graph #on the #problem: On the Complexity of Shortest Path Problems on Discounted Cost Graphs (RA, SK, KT, YY), pp. 44–55.
LATA-2013-BenzaidDE #algorithm: Duplication-Loss Genome Alignment: Complexity and Algorithm (BB, RD, NEM), pp. 116–127.
LATA-2013-Cai #problem: Complexity Dichotomy for Counting Problems (JYC), pp. 1–11.
LATA-2013-DelzannoT #decidability #network #verification: Decidability and Complexity Results for Verification of Asynchronous Broadcast Networks (GD, RT), pp. 238–249.
LATA-2013-FreivaldsZP #automaton #on the: On the Size Complexity of Deterministic Frequency Automata (RF, TZ, GRP), pp. 287–298.
RTA-2013-AvanziniM #framework: A Combination Framework for Complexity (MA, GM), pp. 55–70.
RTA-2013-AvanziniM13a: Tyrolean Complexity Tool: Features and Usage (MA, GM), pp. 71–80.
RTA-2013-Schmidt-SchaussRS #algorithm: Algorithms for Extended α-Equivalence and Complexity (MSS, CR, DS), pp. 255–270.
CHI-2013-LugerMR: Consent for all: revealing the hidden complexity of terms and conditions (EL, SM, TR), pp. 2687–2696.
CHI-2013-ReineckeYMMZLG #predict #quantifier #visual notation: Predicting users’ first impressions of website aesthetics with a quantification of perceived visual complexity and colorfulness (KR, TY, LM, RM, YZ, JL, KZG), pp. 2049–2058.
DHM-HB-2013-LiWZYHZ #variability: Changes in Heart Rate Variability during Manual Controlled Rendezvous and Docking with Task Complexity (PL, BW, YZ, ZY, WH, XZ), pp. 86–92.
DHM-SET-2013-WangZWLCZL #fault: Effects of Spaceflight Operation Complexity and Training on Operation Error (MW, YZ, BW, PL, SC, JZ, ML), pp. 118–125.
HIMI-D-2013-KaoW: The Right Level of Complexity in a Banner Ad: Roles of Construal Level and Fluency (CTK, MYW), pp. 604–613.
CAiSE-2013-Espada0A #framework #modelling: A Framework to Evaluate Complexity and Completeness of KAOS Goal Models (PE, MG, JA), pp. 562–577.
ICEIS-v3-2013-LambeckG #concept #enterprise #scalability #user interface: Mastering ERP Interface Complexity — A Scalable User Interface Concept for ERP Systems (CL, RG), pp. 170–178.
KDD-2013-AbrahaoCKP #network: Trace complexity of network inference (BDA, FC, RK, AP), pp. 491–499.
KDIR-KMIS-2013-CechTBH #modelling #multi: Modelling Complexity of Economic System with Multi-Agent Systems (PC, PT, VB, MH), pp. 464–469.
SEKE-2013-JulianoTSM #assessment #automation #case study #similarity: Automated Computation of Use Cases Similarity can Aid the Assessment of Cohesion and Complexity of Classes (RCJ, BANT, MSS, MdAM), pp. 494–499.
SKY-2013-RineF #information management #metric #quality #representation #requirements #using: Requirements Quality Knowledge Representation using Chunking Complexity Measurement: Prior to Formal Inspections (DCR, AF), pp. 3–13.
QAPL-2013-ArulR #game studies #integer: The Complexity of Robot Games on the Integer Line (AA, JR), pp. 132–148.
ASE-2013-PohlSP #feature model #modelling: Measuring the structural complexity of feature models (RP, VS, KP), pp. 454–464.
DAC-2013-HuKM #coordination: Taming the complexity of coordinated place and route (JH, MCK, ILM), p. 7.
DAC-2013-ZhouLJ #3d #finite #linear #multi #scalability: A direct finite element solver of linear complexity for large-scale 3-D circuit extraction in multiple dielectrics (BZ, HL, DJ), p. 6.
DATE-2013-KhanSGH #collaboration #reduction: Hardware-software collaborative complexity reduction scheme for the emerging HEVC intra encoder (MUKK, MS, MG, JH), pp. 125–128.
DATE-2013-RustLP #architecture #using: Low complexity QR-decomposition architecture using the logarithmic number system (JR, FL, SP), pp. 97–102.
PPoPP-2013-WuZZJS #algorithm #analysis #design #gpu #memory management: Complexity analysis and algorithm design for reorganizing data to minimize non-coalesced memory accesses on GPU (BW, ZZ, EZZ, YJ, XS), pp. 57–68.
FoSSaCS-2013-HainryMP #analysis #process #type system: Type-Based Complexity Analysis for Fork Processes (EH, JYM, RP), pp. 305–320.
FoSSaCS-2013-KarandikarS #parametricity #problem #recursion: The Parametric Ordinal-Recursive Complexity of Post Embedding Problems (PK, SS), pp. 273–288.
STOC-2013-BeiCZ #fault #on the: On the complexity of trial and error (XB, NC, SZ), pp. 31–40.
STOC-2013-BravermanM #approach: An information complexity approach to extended formulations (MB, AM), pp. 161–170.
STOC-2013-BurgisserI #bound #geometry: Explicit lower bounds via geometric complexity theory (PB, CI), pp. 141–150.
STOC-2013-ChenPY: The complexity of non-monotone markets (XC, DP, MY), pp. 181–190.
STOC-2013-SinclairS #theorem: Lee-Yang theorems and the complexity of computing averages (AS, PS), pp. 625–634.
STOC-2013-ThapperZ: The complexity of finite-valued CSPs (JT, SZ), pp. 695–704.
CSL-2013-BulatovDT #approximate: Descriptive complexity of approximate counting CSPs (AAB, VD, MT), pp. 149–164.
CSL-2013-SchmidtW #abduction #constraints #similarity: The Complexity of Abduction for Equality Constraint Languages (JS, MW), pp. 615–633.
LICS-2013-BolligKM #model checking #multi: The Complexity of Model Checking Multi-stack Systems (BB, DK, RM), pp. 163–172.
LICS-2013-FereeHG #on the #query: On the Query Complexity of Real Functionals (HF, MH, WG), pp. 103–112.
LICS-2013-MontanariS #equivalence #logic: Adding an Equivalence Relation to the Interval Logic ABB: Complexity and Expressiveness (AM, PS), pp. 193–202.
SAT-2013-Beyersdorff #logic #proving #theorem proving: The Complexity of Theorem Proving in Autoepistemic Logic (OB), pp. 365–376.
SAT-2013-Toran #graph #morphism #on the: On the Resolution Complexity of Graph Non-isomorphism (JT), pp. 52–66.
DRR-2012-GaoZN #online #recognition #reduction: Complexity reduction with recognition rate maintained for online handwritten Japanese text recognition (JG, BZ, MN).
PODS-2012-DengFG #on the #problem #recommendation: On the complexity of package recommendation problems (TD, WF, FG), pp. 261–272.
PODS-2012-Kimelfeld #dependence #functional: A dichotomy in the complexity of deletion propagation with functional dependencies (BK), pp. 191–202.
PODS-2012-LosemannM: The complexity of evaluating path expressions in SPARQL (KL, WM), pp. 101–112.
VLDB-2012-CautisK #probability #query #using #xml: Answering Queries using Views over Probabilistic XML: Complexity and Tractability (BC, EK), pp. 1148–1159.
VLDB-2012-MamourasOSKG #coordination #social: The Complexity of Social Coordination (KM, SO, LS, LK, JG), pp. 1172–1183.
ITiCSE-2012-BrownPSE #analysis #generative #named: JUG: a JUnit generation, time complexity analysis and reporting tool to streamline grading (CB, RP, BS, JE), pp. 99–104.
CSMR-2012-TerceiroMCC #analysis #comprehension #evolution: Understanding Structural Complexity Evolution: A Quantitative Analysis (ASdAT, MGM, CC, DSC), pp. 85–94.
ICPC-2012-KatzmarskiK #metric: Program complexity metrics and programmer opinions (BK, RK), pp. 17–26.
SCAM-2012-VinjuG #control flow #metric #what: What Does Control Flow Really Look Like? Eyeballing the Cyclomatic Complexity Metric (JJV, MWG), pp. 154–163.
AFL-J-2011-BrzozowskiL12: Quotient Complexity of Star-Free Languages (JAB, BL), pp. 1261–1276.
DLT-J-2011-GaoY12 #approximate: State Complexity and Approximation (YG, SY), pp. 1085–1098.
CIAA-2012-JiraskovaM #on the: On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs (GJ, TM), pp. 229–239.
CIAA-2012-KutribO #automaton #on the: On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata (MK, FO), pp. 253–264.
DLT-2012-GandhiKL #finite #on the #word: On State Complexity of Finite Word and Tree Languages (AG, BK, JL), pp. 392–403.
DLT-2012-JiraskovaS: The State Complexity of Star-Complement-Star (GJ, JS), pp. 380–391.
ICALP-v1-2012-AdaCFN #communication #multi: The NOF Multiparty Communication Complexity of Composed Functions (AA, AC, OF, PN), pp. 13–24.
ICALP-v1-2012-Bauwens: Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexity (BB), pp. 100–108.
ICALP-v1-2012-GoldbergJ #approximate #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-HalldorssonSSW #approximate #clique #communication #streaming: Streaming and Communication Complexity of Clique Approximation (MMH, XS, MS, CW), pp. 449–460.
ICALP-v1-2012-JefferyKM #graph #matrix #multi #quantum #query #using: Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision (SJ, RK, FM), pp. 522–532.
ICALP-v1-2012-LinC: The Parameterized Complexity of k-Edge Induced Subgraphs (BL, YC), pp. 641–652.
ICALP-v2-2012-ChiesaBEP: Computational Complexity of Traffic Hijacking under BGP and S-BGP (MC, GDB, TE, MP), pp. 476–487.
ICALP-v2-2012-Velner #automaton: The Complexity of Mean-Payoff Automaton Expression (YV), pp. 390–402.
LATA-2012-DennunzioFP #automaton: Computational Complexity of Rule Distributions of Non-uniform Cellular Automata (AD, EF, JP), pp. 204–215.
LATA-2012-Downey #tutorial: A Parameterized Complexity Tutorial (RD), pp. 38–56.
LATA-2012-ForisekKS #online: Advice Complexity of Online Coloring for Paths (MF, LK, MS), pp. 228–239.
LATA-2012-MeierSTV #logic #on the: On the Parameterized Complexity of Default Logic and Autoepistemic Logic (AM, JS, MT, HV), pp. 389–400.
RTA-2012-Terui #evaluation #semantics #λ-calculus: Semantic Evaluation, Intersection Types and Complexity of Simply Typed λ Calculus (KT), pp. 323–338.
ICFP-2012-EndrullisHB #equivalence #infinity #on the #specification: On the complexity of equivalence of specifications of infinite objects (JE, DH, RB), pp. 153–164.
CHI-2012-AndersenOLSLTCP #game studies: The impact of tutorials on games of varying complexity (EA, EO, YEL, RS, JL, DT, SC, ZP), pp. 59–68.
CIKM-2012-BlessingS: Crosslingual distant supervision for extracting relations of different complexity (AB, HS), pp. 1123–1132.
ICML-2012-AzarMK #generative #learning #on the: On the Sample Complexity of Reinforcement Learning with a Generative Model (MGA, RM, BK), p. 222.
ICML-2012-MairalY #analysis: Complexity Analysis of the Lasso Regularization Path (JM, BY), p. 238.
ICPR-2012-BaiHHR #clustering #graph #using: Graph clustering using graph entropy complexity traces (LB, ERH, LH, PR), pp. 2881–2884.
ICPR-2012-ChattopadhyayJC #novel #video: A novel low complexity TV video OCR system (TC, RJ, BBC), pp. 665–668.
ICPR-2012-RingJKE #analysis #classification #design #embedded #performance: Software-based performance and complexity analysis for the design of embedded classification systems (MR, UJ, PK, BE), pp. 2266–2269.
KMIS-2012-WongthongthamZ #information management #metric #ontology: Ontology based Knowledge Transferability and Complexity Measurement for Knowledge Sharing (PW, BZ), pp. 5–14.
KR-2012-AdarichevaSST: Horn Belief Contraction: Remainders, Envelopes and Complexity (KVA, RHS, BS, GT).
KR-2012-CalvaneseOSS #query: The Complexity of Explaining Negative Query Answers in DL-Lite (DC, MO, MS, GS).
KR-2012-LutzW #logic #query: Non-Uniform Data Complexity of Query Answering in Description Logics (CL, FW).
KR-2012-VlaeminckVBD #logic #order #semantics: Ordered Epistemic Logic: Semantics, Complexity and Applications (HV, JV, MB, MD).
SEKE-2012-JuniorGM #architecture #empirical #metric #product line #validation #variability: Empirical Validation of Variability-based Complexity Metrics for Software Product Line Architecture (EAdOJ, IMdSG, JCM), pp. 622–627.
SIGIR-2012-ArguelloWKE #interactive: Task complexity, vertical display and user interaction in aggregated search (JA, WCW, DK, AE), pp. 435–444.
REFSQ-2012-GulkeRJA #development #problem #requirements: High-Level Requirements Management and Complexity Costs in Automotive Development Projects: A Problem Statement (TG, BR, MJ, JA), pp. 94–100.
ASE-2012-Nogueira #predict #testing: Predicting software complexity by means of evolutionary testing (AFN), pp. 402–405.
SAC-2012-CombiP #on the #workflow: On the complexity of temporal controllabilities for workflow schemata (CC, RP), pp. 60–66.
DATE-2012-AbeleinLHS #challenge #quality #robust: Complexity, quality and robustness — the challenges of tomorrow’s automotive electronics (UA, HL, DH, SS), pp. 870–871.
DATE-2012-YuBL #adaptation #power management: A complexity adaptive channel estimator for low power (ZY, CHvB, HL), pp. 1531–1536.
PDP-2012-CastilloFC #algorithm #concurrent #detection #linear: A Dynamic Deadlock Detection/Resolution Algorithm with Linear Message Complexity (MC, FF, AC), pp. 175–179.
FoSSaCS-2012-ChenBW #on the #probability #similarity: On the Complexity of Computing Probabilistic Bisimilarity (DC, FvB, JW), pp. 437–451.
FoSSaCS-2012-KieferMOWW #automaton #equivalence #on the #probability #problem: On the Complexity of the Equivalence Problem for Probabilistic Automata (SK, ASM, JO, BW, JW), pp. 467–481.
STOC-2012-Braverman #interactive: Interactive information complexity (MB), pp. 505–524.
STOC-2012-CaiC #csp: Complexity of counting CSP with complex weights (JYC, XC), pp. 909–920.
STOC-2012-DobzinskiV #query: From query complexity to computational complexity (SD, JV), pp. 1107–1116.
STOC-2012-HuynhN #communication #on the #proving #trade-off: On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity (TH, JN), pp. 233–248.
STOC-2012-Larsen: The cell probe complexity of dynamic range counting (KGL), pp. 85–94.
STOC-2012-Sherstov #communication #multi #set: The multiparty communication complexity of set disjointness (AAS), pp. 525–548.
CSL-2012-BaillotL #higher-order: Higher-Order Interpretations and Program Complexity (PB, UDL), pp. 62–76.
CSL-2012-ChrzaszczS #ml: ML with PTIME complexity guarantees (JC, AS), pp. 198–212.
CSL-2012-Cook #proving: Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (SAC), pp. 9–11.
CSL-2012-GrandjeanO: Descriptive complexity for pictures languages (EG, FO), pp. 274–288.
CSL-2012-Makowsky #graph #parametricity: Definability and Complexity of Graph Parameters (JAM), pp. 14–15.
ICLP-J-2012-AlvianoFLM #datalog #decidability #quantifier #semantics: Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues (MA, WF, NL, MM), pp. 701–718.
LICS-2012-GollerJL #first-order: The Complexity of Decomposing Modal and First-Order Theories (SG, JCJ, ML), pp. 325–334.
LICS-2012-HaddadSS #petri net #recursion: The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets (SH, SS, PS), pp. 355–364.
LICS-2012-JainMS: The Complexity of Verbal Languages over Groups (SJ, AM, FS), pp. 405–414.
LICS-2012-Nigam #linear #logic #on the: On the Complexity of Linear Authorization Logics (VN), pp. 511–520.
SAT-2012-CreignouV #problem #satisfiability: Parameterized Complexity of Weighted Satisfiability Problems (NC, HV), pp. 341–354.
SMT-2012-KovasznaiFB #logic #on the: On the Complexity of Fixed-Size Bit-Vector Logics with Binary Encoded Bit-Width (GK, AF, AB), pp. 44–56.
PODS-2011-AntonopoulosMN #xml: The complexity of text-preserving XML transformations (TA, WM, FN), pp. 247–258.
PODS-2011-HeBWN #on the #privacy: On the complexity of privacy-preserving complex event processing (YH, SB, DW, JFN), pp. 165–174.
ITiCSE-2011-MarkhamZ #visualisation: A model for visualizing sentence complexity (SM, YZ), p. 357.
ICPC-2011-TothVBG #metric #predict #process: Adding Process Metrics to Enhance Modification Complexity Prediction (GT, AZV, ÁB, TG), pp. 201–204.
CIAA-J-2010-CuiGKY11: State Complexity of Two Combined Operations: Catenation-Union and Catenation-Intersection (BC, YG, LK, SY), pp. 1797–1812.
DLT-J-2010-BrodaMMR11 #approach #automaton #combinator #on the: On the Average State Complexity of Partial derivative Automata: an analytic Combinatorics Approach (SB, AM, NM, RR), pp. 1593–1606.
DLT-J-2010-HolzerK11: The Complexity of Regular(-like) Expressions (MH, MK), pp. 1533–1548.
DLT-J-2010-JiraskovaM11 #regular expression: Complexity in Union-Free Regular Languages (GJ, TM), pp. 1639–1653.
DLT-J-2010-PribavkinaR11: State Complexity of Code Operators (EVP, ER), pp. 1669–1681.
AFL-2011-BrzozowskiJLS #regular expression: Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages (JAB, GJ, BL, JS), pp. 123–137.
AFL-2011-BrzozowskiL: Quotient Complexity of Star-Free Languages (JAB, BL), pp. 138–152.
CIAA-2011-HolzerKM #nondeterminism: Nondeterministic State Complexity of Star-Free Languages (MH, MK, KM), pp. 178–189.
CIAA-2011-Martyugin #automaton #problem #word: Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata (PM), pp. 238–249.
DLT-2011-BrodaMMR #automaton: The Average Transition Complexity of Glushkov and Partial Derivative Automata (SB, AM, NM, RR), pp. 93–104.
DLT-2011-BrzozowskiY: Syntactic Complexity of Ideal and Closed Languages (JAB, YY), pp. 117–128.
DLT-2011-HolzerJ: Chop Operations and Expressions: Descriptional Complexity Considerations (MH, SJ), pp. 264–275.
DLT-2011-YuG #approximate #research: State Complexity Research and Approximation (SY, YG), pp. 46–57.
ICALP-v1-2011-BockenhauerKKK #on the #problem: On the Advice Complexity of the k-Server Problem (HJB, DK, RK, RK), pp. 207–218.
ICALP-v1-2011-ChaillouxKR #quantum: Quantum Commitments from Complexity Assumptions (AC, IK, BR), pp. 73–85.
ICALP-v1-2011-ElsasserT: Settling the Complexity of Local Max-Cut (Almost) Completely (RE, TT), pp. 171–182.
ICALP-v1-2011-GuoLV #problem #symmetry: The Complexity of Symmetric Boolean Parity Holant Problems — (HG, PL, LGV), pp. 712–723.
ICALP-v1-2011-MagniezNSX #bound #random #recursion: Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority (FM, AN, MS, DX), pp. 317–329.
ICALP-v1-2011-Zhang #bound #communication #on the #power of #quantum: On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity (SZ), pp. 49–60.
LATA-2011-BareckaC #automaton #finite #problem: The Parameterized Complexity of Chosen Problems for Finite Automata on Trees (AB, WC), pp. 129–141.
LATA-2011-ChatterjeeHH #game studies: The Complexity of Request-Response Games (KC, TAH, FH), pp. 227–237.
LATA-2011-OkhotinS #ambiguity #automaton #word: Descriptional Complexity of Unambiguous Nested Word Automata (AO, KS), pp. 414–426.
LATA-2011-RigoV #integer #set: Syntactic Complexity of Ultimately Periodic Sets of Integers (MR, ÉV), pp. 477–488.
LATA-2011-SalomaaSY: Undecidability of the State Complexity of Composed Regular Operations (AS, KS, SY), pp. 489–498.
RTA-2011-MoserS #dependence #framework #multi #proving #recursion #termination: Termination Proofs in the Dependency Pair Framework May Induce Multiple Recursive Derivational Complexity (GM, AS), pp. 235–250.
CIG-2011-AlviA #analysis #game studies: Complexity analysis and playing strategies for Ludo and its variant race games (FA, MAA), pp. 134–141.
DHM-2011-ZhangWZQL #fault: Task Complexity Related Training Effects on Operation Error of Spaceflight Emergency Task (YZ, BW, XZ, WQ, ML), pp. 436–445.
HIMI-v1-2011-OkuboTT #comparison: Comparison between Mathematical Complexity and Human Feeling (MO, AT, ST), pp. 132–141.
IDGD-2011-LiuL #comprehension #performance #towards: Toward Understanding the Relationship between Task Complexity and Task Performance (PL, ZL), pp. 192–200.
CAiSE-2011-FiglL #modelling #process: Cognitive Complexity in Business Process Modeling (KF, RL), pp. 452–466.
ICEIS-v1-2011-LiLC #adaptation #research: Research on Innovation of Shipbuilding Supply Chain Management based on Complexity Adaptive System (GL, CL, YC), pp. 389–395.
KDIR-2011-Dietz: Intellectually Managing Organized Complexity (JLGD), p. 13.
KEOD-2011-KohnMSL #ontology #using: Use of Existing Ontologies as Input for Structural Complexity Management — Reducing the Effort for Analysing and Improving Engineering Systems (AK, MM, HXS, UL), pp. 195–201.
SEKE-2011-GaoGMTBK #analysis #component #configuration management #modelling #testing: Testing Configurable Component-Based Software — Configuration Test Modeling and Complexity Analysis (JG, JG, AM, CT, XB, DCK), pp. 495–502.
LOPSTR-2011-StroderESGF #analysis #linear #prolog #semantics #termination: A Linear Operational Semantics for Termination and Complexity Analysis of ISO Prolog (TS, FE, PSK, JG, CF), pp. 237–252.
POPL-2011-EsparzaG #parallel #source code #thread #verification: Complexity of pattern-based verification for multithreaded programs (JE, PG), pp. 499–510.
PPDP-2011-ColazzoS #precise #type inference #xquery: Precision and complexity of XQuery type inference (DC, CS), pp. 89–100.
SAS-2011-GorogiannisKO #abduction #abstraction: The Complexity of Abduction for Separated Heap Abstractions (NG, MIK, PWO), pp. 25–42.
REFSQ-2011-WnukRB #challenge #development #requirements #scalability: Scaling Up Requirements Engineering — Exploring the Challenges of Increasing Size and Complexity in Market-Driven Software Development (KW, BR, BB), pp. 54–59.
SAC-2011-CederquistD #constraints: Complexity of fairness constraints for the Dolev-Yao attacker model (JC, MTD), pp. 1502–1509.
SAC-2011-Sanchez-GonzalezRGC #control flow #metric #modelling #towards: Towards thresholds of control flow complexity measures for BPMN models (LSG, FR, FG, JC), pp. 1445–1450.
GPCE-2011-SobernigGSZ #api #design #empirical #framework #integration: Comparing complexity of API designs: an exploratory experiment on DSL-based framework integration (SS, PG, MS, UZ), pp. 157–166.
DAC-2011-ChaiJ #equation #linear #matrix: Direct matrix solution of linear complexity for surface integral-equation based impedance extraction of high bandwidth interconnects (WC, DJ), pp. 206–211.
DAC-2011-Kocher #challenge: Complexity and the challenges of securing SoCs (PK), pp. 328–331.
DATE-2011-ReddyCBJ #power management: A low complexity stopping criterion for reducing power consumption in turbo decoders (PR, FC, AB, MJ), pp. 649–654.
FASE-2011-KelsenMG #modelling #using: Models within Models: Taming Model Complexity Using the Sub-model Lattice (PK, QM, CG), pp. 171–185.
FASE-2011-ZhangZL #api #graph: Flow-Augmented Call Graph: A New Foundation for Taming API Complexity (QZ, WZ, MRL), pp. 386–400.
FoSSaCS-2011-BernadetL #normalisation: Complexity of Strongly Normalising λ-Terms via Non-idempotent Intersection Types (AB, SL), pp. 88–107.
STOC-2011-AaronsonA #linear: The computational complexity of linear optics (SA, AA), pp. 333–342.
STOC-2011-BurgisserI #geometry #rank: Geometric complexity theory and tensor rank (PB, CI), pp. 509–518.
STOC-2011-ChakrabartiR #bound #communication: An optimal lower bound on the communication complexity of gap-hamming-distance (AC, OR), pp. 51–60.
STOC-2011-Kopparty #finite #on the: On the complexity of powering in finite fields (SK), pp. 489–498.
STOC-2011-NovocinSV #algorithm: An LLL-reduction algorithm with quasi-linear time complexity: extended abstract (AN, DS, GV), pp. 403–412.
STOC-2011-Sherstov #communication #quantum #query #theorem: Strong direct product theorems for quantum communication and query complexity (AAS), pp. 41–50.
CADE-2011-FredriksonCJ #algorithm #analysis #approximate #behaviour: Dynamic Behavior Matching: A Complexity Analysis and New Approximation Algorithms (MF, MC, SJ), pp. 252–267.
CADE-2011-NoschinskiEG #analysis #dependence #framework #term rewriting: A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems (LN, FE, JG), pp. 422–438.
CSL-2011-DurandS #higher-order #logic #problem #query: Enumeration Complexity of Logical Query Problems with Second-order Variables (AD, YS), pp. 189–202.
CSL-2011-LeCY #formal method #problem: A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem (DTML, SAC, YY), pp. 381–395.
CSL-2011-SchnablS #runtime: The Exact Hardness of Deciding Derivational and Runtime Complexity (AS, JGS), pp. 481–495.
LICS-2011-GollerL #term rewriting #verification: The Complexity of Verifying Ground Tree Rewrite Systems (SG, AWL), pp. 279–288.
LICS-2011-HerrmannZ #quantum #satisfiability: Computational Complexity of Quantum Satisfiability (CH, MZ), pp. 175–184.
LICS-2011-KontinenKLV #dependence #logic: Complexity of Two-Variable Dependence Logic and IF-Logic (JK, AK, PL, JV), pp. 289–298.
LICS-2011-Krokhin #first-order: The Complexity of Evaluating First-Order Sentences over a Fixed Structure (AAK), p. 331.
LICS-2011-Marion #analysis #type system: A Type System for Complexity Flow Analysis (JYM), pp. 123–132.
LICS-2011-Pitassi #overview #proving #state of the art: Propositional Proof Complexity: A Survey on the State of the Art, Including Some Recent Results (TP), p. 119.
SAT-2011-BeyersdorffGL: Parameterized Complexity of DPLL Search Procedures (OB, NG, ML), pp. 5–18.
SAT-2011-Williams #algorithm #bound #satisfiability: Connecting SAT Algorithms and Complexity Lower Bounds (RW), pp. 1–2.
ECSA-2010-ZalewskiK #architecture: Architecture Decision-Making in Support of Complexity Control (AZ, SK), pp. 501–504.
PODS-2010-Jayram #tutorial: Information complexity: a tutorial (TSJ), pp. 159–168.
PODS-2010-MartensNS #design #repository #xml: Schema design for XML repositories: complexity and tractability (WM, MN, TS), pp. 239–250.
VLDB-2011-MeliouGMS #query: The Complexity of Causality and Responsibility for Query Answers and non-Answers (AM, WG, KFM, DS), pp. 34–45.
ICPC-2010-BouwersVLD #architecture: A Cognitive Model for Software Architecture Complexity (EB, JV, CL, AvD), pp. 152–155.
DLT-J-2008-Ada10 #communication #nondeterminism #on the #regular expression: On the Non-Deterministic Communication Complexity of Regular Languages (AA), pp. 479–493.
DLT-J-2008-BassinoGN10 #finite: The Average State Complexity of Rational Operations on Finite Languages (FB, LG, CN), pp. 495–516.
CIAA-2010-CuiGKY: State Complexity of Catenation Combined with Union and Intersection (BC, YG, LK, SY), pp. 95–104.
CIAA-2010-DiekertK #regular expression: Complexity Results and the Growths of Hairpin Completions of Regular Languages (VD, SK), pp. 105–114.
DLT-2010-HolzerK: The Complexity of Regular(-Like) Expressions (MH, MK), pp. 16–30.
DLT-2010-JiraskovaM #regular expression: Complexity in Union-Free Regular Languages (GJ, TM), pp. 255–266.
DLT-2010-PribavkinaR #regular expression: State Complexity of Prefix, Suffix, Bifix and Infix Operators on Regular Languages (EVP, ER), pp. 376–386.
ICALP-v1-2010-BeimelDKW #communication: Choosing, Agreeing, and Eliminating in Communication Complexity (AB, SBD, EK, EW), pp. 451–462.
ICALP-v1-2010-DellHW #exponential #polynomial: Exponential Time Complexity of the Permanent and the Tutte Polynomial (HD, TH, MW), pp. 426–437.
ICALP-v1-2010-JacobsCLM #on the: On the Complexity of Searching in Trees: Average-Case Minimization (TJ, FC, ESL, MM), pp. 527–539.
ICALP-v1-2010-LeeZ #communication #composition #theorem: Composition Theorems in Communication Complexity (TL, SZ), pp. 475–489.
ICALP-v2-2010-BlockiW #privacy #problem: Resolving the Complexity of Some Data Privacy Problems (JB, RW), pp. 393–404.
LATA-2010-AravantinosCP #problem #satisfiability: Complexity of the Satisfiability Problem for a Class of Propositional Schemata (VA, RC, NP), pp. 58–69.
LATA-2010-Brzozowski: Complexity in Convex Languages (JAB), pp. 1–15.
LATA-2010-Lin #calculus: Modal Nonassociative Lambek Calculus with Assumptions: Complexity and Context-Freeness (ZL0), pp. 414–425.
LATA-2010-Zantema: Complexity of Guided Insertion-Deletion in RNA-Editing (HZ), pp. 608–619.
RTA-2010-AvanziniM #runtime: Closing the Gap Between Runtime Complexity and Polytime Computability (MA, GM), pp. 33–48.
RTA-2010-ZanklK #analysis #composition: Modular Complexity Analysis via Relative Complexity (HZ, MK), pp. 385–400.
FLOPS-2010-AvanziniM #analysis #graph grammar: Complexity Analysis by Graph Rewriting (MA, GM), pp. 257–271.
AIIDE-2010-FurtakB #game studies #graph #on the: On the Complexity of Two-Player Attrition Games Played on Graphs (TF, MB).
CIG-2010-HeckelYK: Representational complexity of reactive agents (FWPH, GMY, NSK), pp. 257–264.
ICEIS-AIDSS-2010-TroianoP #modelling: Supporting Complexity in Modeling Bayesian Troubleshooting (LT, DDP), pp. 344–349.
ICML-2010-SzitaS #bound #learning #modelling: Model-based reinforcement learning with nearly tight exploration complexity bounds (IS, CS), pp. 1031–1038.
ICPR-2010-EscolanoLH #network: Heat Flow-Thermodynamic Depth Complexity in Networks (FE, MAL, ERH), pp. 1578–1581.
ICPR-2010-KumarCCAPH #classification #using: Heart Murmur Classification Using Complexity Signatures (DK, PC, RC, MA, RPP, JH), pp. 2564–2567.
KEOD-2010-AustingH #metric #modelling: Complexity Measurement of Product Models (SgA, AH), pp. 404–407.
KR-2010-CreignouST #abduction #set #strict: Complexity of Propositional Abduction for Restricted Sets of Boolean Functions (NC, JS, MT).
KR-2010-PenalozaS #axiom #logic #on the #product line: On the Complexity of Axiom Pinpointing in the EL Family of Description Logics (RP, BS).
SEKE-2010-LeeSB #information management #legacy #visualisation: Knowledge Engineering to Visualize Complexity for Legacy Modernization Planning (SBL, SGS, KSB), pp. 331–334.
SEKE-2010-YastrebenetskyT #metric: Synchronization Complexity Metric (PY, MT), pp. 147–152.
PPDP-2010-TekleL #analysis #datalog #performance #precise #query: Precise complexity analysis for efficient datalog queries (KTT, YAL), pp. 35–44.
SAS-2010-AliasDFG #bound #multi #ranking #source code #termination: Multi-dimensional Rankings, Program Termination, and Complexity Bounds of Flowchart Programs (CA, AD, PF, LG), pp. 117–133.
ICSE-2010-Padua #effectiveness #performance: Measuring complexity, effectiveness and efficiency in software course projects (WP), pp. 545–554.
SAC-2010-ChowdhuryZ #metric #question: Can complexity, coupling, and cohesion metrics be used as early indicators of vulnerabilities? (IC, MZ), pp. 1963–1969.
DAC-2010-YangLW #fault #named: ECR: a low complexity generalized error cancellation rewiring scheme (XY, TKL, YLW), pp. 511–516.
DATE-2010-MaricauG #reliability #simulation #variability: Variability-aware reliability simulation of mixed-signal ICs with quasi-linear complexity (EM, GGEG), pp. 1094–1099.
DATE-2010-ShafiqueMH #adaptation #reduction #using #video: An HVS-based Adaptive Computational Complexity Reduction Scheme for H.264/AVC video encoder using Prognostic Early Mode Exclusion (MS, BM, JH), pp. 1713–1718.
FoSSaCS-2010-CassezMZ #data flow #security: The Complexity of Synchronous Notions of Information Flow Security (FC, RvdM, CZ), pp. 282–296.
STOC-2010-BeameHP #proving: Hardness amplification in proof complexity (PB, TH, TP), pp. 87–96.
STOC-2010-DyerR #csp #on the: On the complexity of #CSP (MED, DR), pp. 725–734.
STOC-2010-GoyalJ #on the: On the round complexity of covert computation (VG, AJ), pp. 191–200.
STOC-2010-KawamuraC #analysis: Complexity theory for operators in analysis (AK, SAC), pp. 495–502.
STOC-2010-PaturiP #on the #satisfiability: On the complexity of circuit satisfiability (RP, PP), pp. 241–250.
CSL-2010-EickmeyerG: Randomisation and Derandomisation in Descriptive Complexity Theory (KE, MG), pp. 275–289.
CSL-2010-LohmannV #dependence #logic: Complexity Results for Modal Dependence Logic (PL, HV), pp. 411–425.
CSL-2010-MartinM #first-order #logic #similarity: The Complexity of Positive First-Order Logic without Equality II: The Four-Element Case (BM, JM), pp. 426–438.
IJCAR-2010-Benthem #logic: Logic between Expressivity and Complexity (JvB), pp. 122–126.
LICS-2010-KopczynskiT #image: Parikh Images of Grammars: Complexity and Applications (EK, AWT), pp. 80–89.
LICS-2010-KreutzerT #bound #higher-order #logic #monad: Lower Bounds for the Complexity of Monadic Second-Order Logic (SK, ST), pp. 189–198.
SAT-2010-BeyersdorffMMTV #logic #proving: Proof Complexity of Propositional Default Logic (OB, AM, SM, MT, HV), pp. 30–43.
SAT-2010-Paturi #algorithm: Exact Algorithms and Complexity (RP), pp. 8–9.
SAT-2010-PorschenSS #linear #problem: Complexity Results for Linear XSAT-Problems (SP, TS, ES), pp. 251–263.
VMCAI-2010-ChadhaLPV #bound #realtime #verification: Complexity Bounds for the Verification of Real-Time Software (RC, AL, PP, MV), pp. 95–111.
WICSA-ECSA-2009-SangwanN #architecture: Characterizing essential and incidental complexity in software architectures (RSS, CJN), pp. 265–268.
PODS-2009-Parys #evaluation #linear #polynomial #xpath: XPath evaluation in linear time with polynomial combined complexity (PP), pp. 55–64.
ICPC-J-2008-HindleGH09 #rank #using: Reading beside the lines: Using indentation to rank revisions by complexity (AH, MWG, RCH), pp. 414–429.
CSMR-2009-CapiluppiB #case study: Structural Complexity and Decay in FLOSS Systems: An Inter-repository Study (AC, KB), pp. 169–178.
CSMR-2009-Lilienthal #architecture #scalability: Architectural Complexity of Large-Scale Software Systems (CL), pp. 17–26.
CIAA-J-2008-HolzerK09 #automaton #finite #nondeterminism: Nondeterministic Finite Automata — Recent Results on the Descriptional and Computational Complexity (MH, MK), pp. 563–580.
DLT-2009-BlakeleyBGR #on the #set #word: On the Complexity of Deciding Avoidability of Sets of Partial Words (BB, FBS, JG, NR), pp. 113–124.
DLT-2009-DurandP: Asymptotic Cellular Complexity (BD, VP), pp. 195–206.
DLT-2009-GruberH #bound #regular expression: Tight Bounds on the Descriptional Complexity of Regular Expressions (HG, MH), pp. 276–287.
DLT-2009-Kapoutsis #automaton #finite: Size Complexity of Two-Way Finite Automata (CAK), pp. 47–66.
DLT-2009-Saarela #equation #on the #satisfiability #theorem: On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations (AS), pp. 443–453.
ICALP-v1-2009-ChandranGR #linear: The Tile Complexity of Linear Assemblies (HC, NG, JHR), pp. 235–253.
ICALP-v1-2009-DraismaKW #communication #multi: Partition Arguments in Multiparty Communication Complexity (JD, EK, EW), pp. 390–402.
ICALP-v1-2009-DurandRS #fault: High Complexity Tilings with Sparse Errors (BD, AER, AS), pp. 403–414.
ICALP-v1-2009-RolandS #communication: Amortized Communication Complexity of Distributions (JR, MS), pp. 738–749.
ICALP-v2-2009-KobayashiO #calculus #model checking #recursion #μ-calculus: Complexity of Model Checking Recursion Schemes for Fragments of the Modal μ-Calculus (NK, CHLO), pp. 223–234.
ICALP-v2-2009-UmmelsW #game studies #multi #nash #probability: The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games (MU, DW), pp. 297–308.
LATA-2009-BeyersdorffKM #nondeterminism #proving: Nondeterministic Instance Complexity and Proof Systems with Advice (OB, JK, SM), pp. 164–175.
LATA-2009-Bollig #bound #integer #multi: Larger Lower Bounds on the OBDD Complexity of Integer Multiplication (BB), pp. 212–223.
LATA-2009-HanSY #regular expression: State Complexity of Combined Operations for Prefix-Free Regular Languages (YSH, KS, SY), pp. 398–409.
LATA-2009-HolzerK #automaton #finite: Descriptional and Computational Complexity of Finite Automata (MH, MK), pp. 23–42.
LATA-2009-LiuM #automation: Analysing Complexity in Classes of Unary Automatic Structures (JL, MM), pp. 518–529.
LATA-2009-Llull-ChavarriaV #semantics #word: An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words (JLC, OV), pp. 530–541.
LATA-2009-Salimov #infinity #word: Constructing Infinite Words of Intermediate Arithmetical Complexity (PVS), pp. 696–701.
LATA-2009-Salomaa #automaton #word: State Complexity of Nested Word Automata (KS), pp. 59–70.
FM-2009-BonakdarpourK #bound #on the: On the Complexity of Synthesizing Relaxed and Graceful Bounded-Time 2-Phase Recovery (BB, SSK), pp. 660–675.
RTA-2009-MoserS #dependence: The Derivational Complexity Induced by the Dependency Pair Method (GM, AS), pp. 255–269.
TLCA-2009-WilkenW: Complexity of Gödel’s T in λ-Formulation (GW, AW), pp. 386–400.
DiGRA-2009-Kerr #game studies: Levels of Complexity: Cultural Diversity, Politics and Digital Games [Abstract] (AK).
FDG-2009-Claypool #game studies #streaming #video: Motion and scene complexity for streaming video games (MC), pp. 34–41.
DHM-2009-BensonR: Complexity of Sizing for Space Suit Applications (EB, SR), pp. 599–607.
ICEIS-HCI-2009-NakanishiTO #artificial reality #design #effectiveness #guidelines #using #verification: Study for Establishing Design Guidelines for Manuals using Augmented Reality Technology — Verification and Expansion of the Basic Model Describing “Effective Complexity” (MN, SiT, YO), pp. 21–26.
KDIR-2009-Ivanko: A Simple Measure of the Kolmogorov Complexity (EI), pp. 5–9.
KEOD-2009-AnderlMS #approach #optimisation #reduction: An Approach to Support Interdisciplinary Variant Diversity Optimization — Planning Variant Diversity — Beyond Complexity Reduction (RA, SM, DS), pp. 408–411.
POPL-2009-GulwaniMC #estimation #named #performance #precise: SPEED: precise and efficient static estimation of program computational complexity (SG, KKM, TMC), pp. 127–139.
SAS-2009-SridharanF #analysis: The Complexity of Andersen’s Analysis in Practice (MS, SJF), pp. 205–221.
ICSE-2009-BurnimJS #automation #generative #named #testing #worst-case: WISE: Automated test generation for worst-case complexity (JB, SJ, KS), pp. 463–473.
ICSE-2009-Hassan #fault #predict #using: Predicting faults using the complexity of code changes (AEH), pp. 78–88.
SAC-2009-KerschbaumDSB #communication #multi #on the #protocol: On the practical importance of communication complexity for secure multi-party computation protocols (FK, DD, AS, DB), pp. 2008–2015.
SAC-2009-LiuTS #classification #learning #using: Assessing complexity of service-oriented computing using learning classifier systems (LL, ST, HS), pp. 2170–2171.
SAC-2009-Stanclova #on the: On the complexity of hierarchical associative memories (JS), pp. 908–913.
DAC-2009-Anderson #design #risk management: Beyond innovation: dealing with the risks and complexity of processor design in 22nm (CJA), p. 103.
DAC-2009-ChaiJK #3d #equation #linear #scalability: A direct integral-equation solver of linear complexity for large-scale 3D capacitance and impedance extraction (WC, DJ, CKK), pp. 752–757.
STOC-2009-DworkNRRV #algorithm #on the #performance: On the complexity of differentially private data release: efficient algorithms and hardness results (CD, MN, OR, GNR, SPV), pp. 381–390.
STOC-2009-KushilevitzW #communication #on the: On the complexity of communication complexity (EK, EW), pp. 465–474.
TACAS-2009-FarzanM #predict: The Complexity of Predicting Atomicity Violations (AF, PM), pp. 155–169.
CADE-2009-EndrullisGH: Complexity of Fractran and Productivity (JE, CG, DH), pp. 371–387.
CADE-2009-LahiriQ #abstraction #algorithm: Complexity and Algorithms for Monomial and Clausal Predicate Abstraction (SKL, SQ), pp. 214–229.
CAV-2009-Gulwani #analysis #bound #named: SPEED: Symbolic Complexity Bound Analysis (SG), pp. 51–62.
CSL-2009-Weber #logic #on the: On the Complexity of Branching-Time Logics (VW), pp. 530–545.
ICLP-2009-Sneyers #compilation #constraints #optimisation: Optimizing Compilation and Computational Complexity of Constraint Handling Rules (JS), pp. 494–498.
LICS-2009-BulatovM #constraints: The Complexity of Global Cardinality Constraints (AAB, DM), pp. 419–428.
LICS-2009-DurandHN: Trichotomy in the Complexity of Minimal Inference (AD, MH, GN), pp. 387–396.
LICS-2009-GollerMT #on the #process #verification: On the Computational Complexity of Verifying One-Counter Processes (SG, RM, AWT), pp. 235–244.
LICS-2009-KazakovP #logic #problem #satisfiability: A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics (YK, IPH), pp. 407–416.
LICS-2009-MadelaineM #first-order #logic #similarity: The Complexity of Positive First-order Logic without Equality (FRM, BM), pp. 429–438.
SAT-2009-BeyersdorffMTV #logic #reasoning: The Complexity of Reasoning for Fragments of Default Logic (OB, AM, MT, HV), pp. 51–64.
SAT-2009-Szeider #satisfiability: The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT (SS), pp. 276–283.
PODS-2008-FanGGNP #composition #web #web service: Complexity and composition of synthesized web services (WF, FG, WG, FN, AP), pp. 231–240.
PODS-2008-SenellartG #database #on the: On the complexity of deriving schema mappings from database instances (PS, GG), pp. 23–32.
ICPC-2008-HindleGH #metric: Reading Beside the Lines: Indentation as a Proxy for Complexity Metric (AH, MWG, RCH), pp. 133–142.
DLT-J-2007-HanS08 #finite: State Complexity of Union and Intersection of Finite Languages (YSH, KS), pp. 581–595.
AFL-2008-Martyugin #automaton #commutative #problem #word: Complexity of problems concerning reset words for commutative automata and automata with simple idempotents (PVM), pp. 314–324.
CIAA-2008-DolzhenkoJ #2d #on the #transducer: On Complexity of Two Dimensional Languages Generated by Transducers (ED, NJ), pp. 181–190.
CIAA-2008-HolzerK #finite #nondeterminism: Nondeterministic Finite Automata-Recent Results on the Descriptional and Computational Complexity (MH, MK), pp. 1–16.
DLT-2008-Ada #communication #nondeterminism #on the #regular expression: On the Non-deterministic Communication Complexity of Regular Languages (AA), pp. 96–107.
DLT-2008-BassinoGN #finite #linear #set #word: The Average State Complexity of the Star of a Finite Set of Words Is Linear (FB, LG, CN), pp. 134–145.
DLT-2008-CassaigneKZ #sequence: Relationally Periodic Sequences and Subword Complexity (JC, TK, LQZ), pp. 196–205.
DLT-2008-Jiraskova #on the #regular expression: On the State Complexity of Complements, Stars, and Reversals of Regular Languages (GJ), pp. 431–442.
DLT-2008-JiraskovaO #automaton #finite #on the: On the State Complexity of Operations on Two-Way Finite Automata (GJ, AO), pp. 443–454.
DLT-2008-KapoutsisKM #automaton #on the: On the Size Complexity of Rotating and Sweeping Automata (CAK, RK, TM), pp. 455–466.
DLT-2008-SelivanovW: Complexity of Topological Properties of Regular ω-Languages (VLS, KWW), pp. 529–542.
ICALP-A-2008-AndoniK #distance #edit distance: The Smoothed Complexity of Edit Distance (AA, RK), pp. 357–369.
ICALP-A-2008-BuchfuhrerU: The Complexity of Boolean Formula Minimization (DB, CU), pp. 24–35.
ICALP-A-2008-Bulatov #constraints #problem: The Complexity of the Counting Constraint Satisfaction Problem (AAB), pp. 646–661.
ICALP-A-2008-ChengW: Complexity of Decoding Positive-Rate Reed-Solomon Codes (QC, DW), pp. 283–293.
ICALP-A-2008-ChenTW #comprehension #morphism: Understanding the Complexity of Induced Subgraph Isomorphisms (YC, MT, MW), pp. 587–596.
ICALP-A-2008-FialaGK #distance #problem: Computational Complexity of the Distance Constrained Labeling Problem for Trees (JF, PAG, JK), pp. 294–305.
ICALP-A-2008-Yin #nondeterminism #proving: Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity (YY), pp. 72–83.
ICALP-B-2008-BodirskyG #constraints: Non-dichotomies in Constraint Satisfaction Complexity (MB, MG), pp. 184–196.
ICALP-B-2008-BouyerMOW #model checking #on the #realtime: On Expressiveness and Complexity in Real-Time Model Checking (PB, NM, JO, JW), pp. 124–135.
ICALP-C-2008-KatzKK #network: Improving the Round Complexity of VSS in Point-to-Point Networks (JK, CYK, RK), pp. 499–510.
FLOPS-2008-AvanziniM #analysis: Complexity Analysis by Rewriting (MA, GM), pp. 130–146.
KR-2008-Bienvenu #abduction #lightweight #logic #product line: Complexity of Abduction in the EL Family of Lightweight Description Logics (MB), pp. 220–230.
KR-2008-EyerichBN #on the: On the Complexity of Planning Operator Subsumption (PE, MB, BN), pp. 518–527.
KR-2008-RenzL #automation #calculus #proving: Automated Complexity Proofs for Qualitative Spatial and Temporal Calculi (JR, JJL), pp. 715–723.
SEKE-2008-GaoKF #analysis #modelling #testing: Model-based Test Complexity Analysis for Software Installation Testing (JG, KK, TF), pp. 631–637.
MoDELS-2008-MorinVLGBJ #aspect-oriented #modelling #variability: Managing Variability Complexity in Aspect-Oriented Modeling (BM, GV, PL, AG, OB, JMJ), pp. 797–812.
MoDELS-2008-MorinVLGBJ #aspect-oriented #modelling #variability: Managing Variability Complexity in Aspect-Oriented Modeling (BM, GV, PL, AG, OB, JMJ), pp. 797–812.
POPL-2008-Danielsson #analysis #data type #functional #lightweight: Lightweight semiformal time complexity analysis for purely functional data structures (NAD), pp. 133–144.
PPDP-2008-MarionP #polynomial: Characterizations of polynomial complexity classes with a better intensionality (JYM, RP), pp. 79–88.
REFSQ-2008-RegnellBW #question #requirements #scalability: Can We Beat the Complexity of Very Large-Scale Requirements Engineering? (BR, RBS, KW), pp. 123–128.
DATE-2008-LeppeltB: Determining the Technical Complexity of Integrated Circuits (PL, EB), p. 935.
DATE-2008-MoserTBB #robust: Robust and Low Complexity Rate Control for Solar Powered Sensors (CM, LT, DB, LB), pp. 230–235.
DATE-2008-ScheerSB #reduction #standard: CARbridge, Reduction of System Complexity by Standardisation of the System-Basis-Chips for Automotive Applications (PS, ES, SB), pp. 1107–1110.
FoSSaCS-2008-AntonikHLNW #problem #specification: Complexity of Decision Problems for Mixed and Modal Specifications (AA, MH, KGL, UN, AW), pp. 112–126.
FoSSaCS-2008-Bozzelli #linear: The Complexity of CTL* + Linear Past (LB), pp. 186–200.
FoSSaCS-2008-GruberJ #bound #communication #regular expression #using: Optimal Lower Bounds on Regular Expression Size Using Communication Complexity (HG, JJ), pp. 273–286.
FoSSaCS-2008-Ummels #game studies #infinity #multi #nash: The Complexity of Nash Equilibria in Infinite Multiplayer Games (MU), pp. 20–34.
STOC-2008-AaronsonW #named: Algebrization: a new barrier in complexity theory (SA, AW), pp. 731–740.
STOC-2008-BartoKN #graph #morphism #problem: Graphs, polymorphisms and the complexity of homomorphism problems (LB, MK, TN), pp. 789–796.
STOC-2008-BodirskyK #constraints #problem: The complexity of temporal constraint satisfaction problems (MB, JK), pp. 29–38.
STOC-2008-ChoiK #bound #graph #query: Optimal query complexity bounds for finding graphs (SSC, JHK), pp. 749–758.
STOC-2008-JainKN #bound #communication #theorem: Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract (RJ, HK, AN), pp. 599–608.
STOC-2008-Rossman #clique #on the: On the constant-depth complexity of k-clique (BR), pp. 721–730.
CSL-2008-DawarG #game studies: The Descriptive Complexity of Parity Games (AD, EG), pp. 354–368.
IJCAR-2008-AvanziniMS #analysis #automation: Automated Implicit Computational Complexity Analysis (MA, GM, AS), pp. 132–138.
IJCAR-2008-HirokawaM #analysis #automation #dependence: Automated Complexity Analysis Based on the Dependency Pair Method (NH, GM), pp. 364–379.
IJCAR-2008-Lutz #logic #query: The Complexity of Conjunctive Query Answering in Expressive Description Logics (CL), pp. 179–193.
LICS-2008-AehligB #on the: On the Computational Complexity of Cut-Reduction (KA, AB), pp. 284–293.
LICS-2008-ChadhaSV #finite #monitoring #on the: On the Expressiveness and Complexity of Randomization in Finite State Monitors (RC, APS, MV), pp. 18–29.
LICS-2008-ChambartS #recursion: The Ordinal Recursive Complexity of Lossy Channel Systems (PC, PS), pp. 205–216.
LICS-2008-Riis #calculus #on the #polynomial #proving: On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity (SR), pp. 272–283.
SAT-2008-Gao #algorithm #problem #random: Random Instances of W[2]-Complete Problems: Thresholds, Complexity, and Algorithms (YG), pp. 91–104.
SAT-2008-GeorgiouP #algorithm #satisfiability: Complexity and Algorithms for Well-Structured k-SAT Instances (KG, PAP), pp. 105–118.
PODS-2007-CateL #query #xpath: The complexity of query containment in expressive fragments of XPath 2.0 (BtC, CL), pp. 73–82.
PODS-2007-FanGN #transducer #xml: Expressiveness and complexity of xml publishing transducers (WF, FG, FN), pp. 83–92.
PODS-2007-KasneciS #reasoning #xml: The complexity of reasoning about pattern-based XML schemas (GK, TS), pp. 155–164.
PODS-2007-SenellartA #on the #probability #xml: On the complexity of managing probabilistic XML data (PS, SA), pp. 283–292.
ITiCSE-2007-BureaC: Complexity of ambient intelligence in managerial work (VB, PC), p. 325.
SIGITE-2007-RigbyDER: Preparing IAS graduates to recognize and manage complexity (SR, MJD, JJE, MKR), pp. 245–252.
ICPC-2007-Vivanco #algorithm #identification #metric #modelling #predict #search-based #source code #using: Use of a Genetic Algorithm to Identify Source Code Metrics Which Improves Cognitive Complexity Predictive Models (RAV), pp. 297–300.
CIAA-J-2006-SalomaaY07 #estimation #on the: On the State Complexity of Combined Operations and their Estimation (KS, SY), pp. 683–698.
DLT-2007-GruberH #exclamation #nondeterminism: Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP (HG, MH), pp. 205–216.
DLT-2007-HanS #finite: State Complexity of Union and Intersection of Finite Languages (YSH, KS), pp. 217–228.
DLT-2007-LoosO: Complexity Theory for Splicing Systems (RL, MO), pp. 300–311.
DLT-2007-MalcherP #bound #context-free grammar: Descriptional Complexity of Bounded Context-Free Languages (AM, GP), pp. 312–323.
DLT-2007-Salomaa #automaton #finite #nondeterminism: Descriptional Complexity of Nondeterministic Finite Automata (KS), pp. 31–35.
ICALP-2007-BeameDPW #communication #multi #nondeterminism: Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity (PB, MD, TP, PW), pp. 134–145.
ICALP-2007-BienvenuM: Reconciling Data Compression and Kolmogorov Complexity (LB, WM), pp. 643–654.
ICALP-2007-BlaserD #polynomial: Complexity of the Cover Polynomial (MB, HD), pp. 801–812.
ICALP-2007-BurgisserC #problem #quantifier: Exotic Quantifiers, Complexity Classes, and Complete Problems (PB, FC), pp. 207–218.
ICALP-2007-DershowitzT #proving: Complexity of Propositional Proofs Under a Promise (ND, IT), pp. 291–302.
ICALP-2007-IwamaNRY #bound #communication #quantum: Unbounded-Error One-Way Classical and Quantum Communication Complexity (KI, HN, RR, SY), pp. 110–121.
ICALP-2007-LuTW #on the #set: On the Complexity of Hard-Core Set Constructions (CJL, SCT, HLW), pp. 183–194.
ICALP-2007-MontanaroW #bound #communication #quantum: A Lower Bound on Entanglement-Assisted Quantum Communication Complexity (AM, AJW), pp. 122–133.
ICALP-2007-TorreP #model checking #on the #recursion #state machine: On the Complexity of LtlModel-Checking of Recursive State Machines (SLT, GP), pp. 937–948.
LATA-2007-AblayevG #branch #quantum #simulation #source code: Classical Simulation Complexity of Quantum Branching Programs (FMA, AG), pp. 49–56.
LATA-2007-GruberH #automaton #finite #nondeterminism: Computational Complexity of NFA Minimization for Finite and Unary Languages (HG, MH), pp. 261–272.
LATA-2007-LenaM #automaton: Computational Complexity of Dynamical Systems: the case of Cellular Automata (PdL, LM), pp. 211–222.
LATA-2007-LiuMSY: State Complexity of Basic Operations Combined with Reversal (GL, CMV, AS, SY), pp. 355–366.
LATA-2007-MasopustM: Descriptional Complexity of Grammars Regulated by Context Conditions (TM, AM), pp. 403–412.
LATA-2007-Povarov #regular expression: Descriptive Complexity of the Hamming Neighborhood of a Regular Language (GP), pp. 509–520.
ICFP-2007-HornM #analysis #control flow #precise: Relating complexity and precision in control flow analysis (DVH, HGM), pp. 85–96.
IFL-2007-DijkstraFS #compilation #haskell: The Structure of the Essential Haskell Compiler, or Coping with Compiler Complexity (AD, JF, SDS), pp. 57–74.
DHM-2007-DeLaurentis: Role of Humans in Complexity of a System-of-Systems (DD), pp. 363–371.
DHM-2007-XuWZZ #algorithm #predict: An Epileptic Seizure Prediction Algorithm from Scalp EEG Based on Morphological Filter and Kolmogorov Complexity (GX, JW, QZ, JZ), pp. 736–746.
HCI-AS-2007-Song #analysis #segmentation #visual notation #web: Analysis of Web Page Complexity Through Visual Segmentation (GS), pp. 114–123.
HCI-AS-2007-UflackerB #enterprise #experience #user interface: Complexity in Enterprise Applications vs. Simplicity in User Experience (MU, DKB), pp. 778–787.
HCI-AS-2007-Xing: Information Complexity in Air Traffic Control Displays (JX), pp. 797–806.
HCI-IDU-2007-LingLX #using #validation #web: Validating Information Complexity Questionnaires Using Travel Web Sites (CL, ML, JX), pp. 901–910.
HCI-MIE-2007-DongLH #segmentation #user interface: Effect of Glance Duration on Perceived Complexity and Segmentation of User Interfaces (YD, CL, LH), pp. 605–614.
HCI-MIE-2007-Sarter #adaptation #design #interface: Coping with Complexity Through Adaptive Interface Design (NBS), pp. 493–498.
HIMI-IIE-2007-FuCS #web: Measuring the Screen Complexity of Web Pages (FLF, SYC, CHS), pp. 720–729.
ICML-2007-Hanneke #bound #learning: A bound on the label complexity of agnostic active learning (SH), pp. 353–360.
SPLC-2007-MebaneO #product line: Dynamic Complexity and the Owen Firmware Product Line Program (HM, JTO), pp. 212–222.
ESEC-FSE-2007-GoldsmithAW #empirical: Measuring empirical computational complexity (SG, AA, DSW), pp. 395–404.
CGO-2007-BouchezDR #on the: On the Complexity of Register Coalescing (FB, AD, FR), pp. 102–114.
DATE-2007-BrackALKWLRRF #generative #standard: Low complexity LDPC code decoders for next generation standards (TB, MA, TLE, FK, NW, NEL, FR, MR, LF), pp. 331–336.
LCTES-2007-BouchezDR #on the: On the complexity of spill everywhere under SSA form (FB, AD, FR), pp. 103–112.
PDP-2007-GalletRV #algorithm #communication #scheduling #traversal: Scheduling Communication Requests Traversing a Switch: Complexity and Algorithms (MG, YR, FV), pp. 39–46.
FoSSaCS-2007-BaulandSSSV #linear #logic #satisfiability: The Complexity of Generalized Satisfiability for Linear Temporal Logic (MB, TS, HS, IS, HV), pp. 48–62.
FoSSaCS-2007-LaroussinieMO #atl #on the: On the Expressiveness and Complexity of ATL (FL, NM, GO), pp. 243–257.
FoSSaCS-2007-TozawaM #context-free grammar: Complexity Results on Balanced Context-Free Languages (AT, YM), pp. 346–360.
STOC-2007-Basu #combinator #geometry: Combinatorial complexity in O-minimal geometry (SB), pp. 47–56.
STOC-2007-Dantchev #proving #rank: Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems (SSD), pp. 311–317.
STOC-2007-GavinskyKKRW #communication #encryption #exponential #quantum: Exponential separations for one-way quantum communication complexity, with applications to cryptography (DG, JK, IK, RR, RdW), pp. 516–525.
STOC-2007-HartM #communication #equilibrium #nash: The communication complexity of uncoupled nash equilibrium procedures (SH, YM), pp. 345–353.
STOC-2007-LinialS #bound #communication: Lower bounds in communication complexity based on factorization norms (NL, AS), pp. 699–708.
TACAS-2007-RasmussenBL #flexibility: Complexity in Simplicity: Flexible Agent-Based State Space Exploration (JIR, GB, KGL), pp. 231–245.
CSL-2007-AehligCN: Relativizing Small Complexity Classes and Their Theories (KA, SAC, PN), pp. 374–388.
CSL-2007-Beckmann #proving #source code: Proofs, Programs and Abstract Complexity (AB), pp. 4–5.
CSL-2007-Goller #on the #policy #reasoning: On the Complexity of Reasoning About Dynamic Policies (SG), pp. 358–373.
ICLP-2007-Nguyen #approximate #knowledge base #logic: Approximating Horn Knowledge Bases in Regular Description Logics to Have PTIME Data Complexity (LAN), pp. 438–439.
LICS-2007-BaillotCL #logic #reduction: Light Logics and Optimal Reduction: Completeness and Complexity (PB, PC, UDL), pp. 421–430.
LICS-2007-NguyenC #proving #theorem: The Complexity of Proving the Discrete Jordan Curve Theorem (PN, SAC), pp. 245–256.
PODS-2006-KolaitisPT: The complexity of data exchange (PGK, JP, WCT), pp. 30–39.
CIAA-2006-MesserschmidtMOP #correctness: Correctness Preservation and Complexity of Simple RL-Automata (HM, FM, FO, MP), pp. 162–172.
CIAA-2006-Yu #on the: On the State Complexity of Combined Operations (SY), pp. 11–22.
DLT-2006-Borel #3d #word: Complexity of Degenerated Three Dimensional Billiard Words (JPB), pp. 386–396.
DLT-2006-GruberH #bound #nondeterminism: Finding Lower Bounds for Nondeterministic State Complexity Is Hard (HG, MH), pp. 363–374.
DLT-2006-Shur #combinator: Factorial Languages of Low Combinatorial Complexity (AMS), pp. 397–407.
ICALP-v1-2006-ChenD #2d #fixpoint #on the #problem: On the Complexity of 2D Discrete Fixed Point Problem (XC, XD), pp. 489–500.
ICALP-v1-2006-DaskalakisFP #game studies #nash: The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games (CD, AF, CHP), pp. 513–524.
ICALP-v1-2006-FortnowHPVW: Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws (LF, JMH, AP, NVV, FW), pp. 335–345.
ICALP-v1-2006-UchizawaDM #energy: Energy Complexity and Entropy of Threshold Circuits (KU, RJD, WM), pp. 631–642.
ICALP-v2-2006-BonattiLMV #calculus #μ-calculus: The Complexity of Enriched μ-Calculi (PAB, CL, AM, MYV), pp. 540–551.
ICALP-v2-2006-Jurdzinski #on the #problem #safety: On Complexity of Grammars Related to the Safety Problem (TJ), pp. 432–443.
CIG-2006-TeramotoDU #game studies #graph: Voronoi game on graphs and its complexity (ST, EDD, RU), pp. 265–271.
ECIR-2006-VinayCMW #documentation: Measuring the Complexity of a Collection of Documents (VV, IJC, NMF, KRW), pp. 107–118.
ICML-2006-ReyzinS #classification #how: How boosting the margin can also boost classifier complexity (LR, RES), pp. 753–760.
ICPR-v1-2006-ChenCW #image: LBT Based Low Complexity Image Compression Method (BC, LC, HW), pp. 941–944.
ICPR-v2-2006-LiuSXR #feature model #image: Image Complexity and Feature Extraction for Steganalysis of LSB Matching Steganography (QL, AHS, JX, BR), pp. 267–270.
ICPR-v2-2006-SuBC #2d #adaptation: Scale Adaptive Complexity Measure of 2D Shapes (HS, AB, DC), pp. 134–137.
ICPR-v3-2006-HuS: Regularity and Complexity of Human Electroencephalogram Dynamics: Applications to Diagnosis of Alzheimers Disease (ZH, PS), pp. 245–248.
ICPR-v4-2006-JiaQ: Improved Stone’s Complexity Pursuit for Hyperspectral Imagery Unmixing (SJ, YQ), pp. 817–820.
KR-2006-CalvaneseGLLR #logic #query: Data Complexity of Query Answering in Description Logics (DC, GDG, DL, ML, RR), pp. 260–270.
RE-2006-DanevaW #coordination #enterprise #requirements: A Coordination Complexity Model to Support Requirements Engineering for Cross-organizational ERP (MD, RW), pp. 304–307.
ASE-2006-MancinelliBCVDLT #open source #scalability: Managing the Complexity of Large Free and Open Source Package-Based Software Distributions (FM, JB, RDC, JV, BD, XL, RT), pp. 199–208.
SAC-2006-BodhuinCPT #physics: Hiding complexity and heterogeneity of the physical world in smart living environments (TB, GC, RP, MT), pp. 1921–1927.
CASE-2006-XingTXH #concurrent #flexibility #policy #polynomial: Optimal Polynomial Complexity Deadlock Avoidance Policies for Manufacturing Systems with Flexible Routings (KX, FT, HX, BH), pp. 448–453.
DATE-2006-NascimentoL #architecture #clustering #configuration management #image: Temporal partitioning for image processing based on time-space complexity in reconfigurable architectures (PSBdN, MEdL), pp. 375–380.
DATE-2006-SrinivasanC #architecture #design #heuristic: A low complexity heuristic for design of custom network-on-chip architectures (KS, KSC), pp. 130–135.
STOC-2006-DaskalakisGP #equilibrium #nash: The complexity of computing a Nash equilibrium (CD, PWG, CHP), pp. 71–78.
STOC-2006-DubrovI #on the #performance: On the randomness complexity of efficient sampling (BD, YI), pp. 711–720.
STOC-2006-GavinskyKRW #bound #communication #exponential #identification #quantum: Bounded-error quantum state identification and exponential separations in communication complexity (DG, JK, OR, RdW), pp. 594–603.
CAV-2006-BustanH: Some Complexity Results for SystemVerilog Assertions (DB, JH), pp. 205–218.
CSL-2006-ArtemovK #logic #proving: Logical Omniscience Via Proof Complexity (SNA, RK), pp. 135–149.
LICS-2006-Lago #linear #logic #semantics: Context Semantics, Linear Logic and Computational Complexity (UDL), pp. 169–178.
LICS-2006-LaurentF #bound #clique #semantics: Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity (OL, LTdF), pp. 179–188.
SAT-2006-BubeckB #dependence #modelling #quantifier: Dependency Quantified Horn Formulas: Models and Complexity (UB, HKB), pp. 198–211.
SAT-2006-KojevnikovK #algebra #proving #strict: Complexity of Semialgebraic Proofs with Restricted Degree of Falsity (AK, ASK), pp. 11–21.
SAT-2006-ZabiyakaD #bound #dependence #functional: Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies (YZ, AD), pp. 116–129.
VMCAI-2006-Bozzelli #automaton #model checking: Complexity Results on Branching-Time Pushdown Model Checking (LB), pp. 65–79.
PODS-2005-HershbergerSST #data type #multi: Space complexity of hierarchical heavy hitters in multi-dimensional data streams (JH, NS, SS, CDT), pp. 338–347.
PODS-2005-Koch #functional #on the #query #recursion #xquery: On the complexity of nonrecursive XQuery and functional query languages on complex values (CK), pp. 84–97.
PODS-2005-LeindersB #algebra #on the #relational #set: On the complexity of division and set joins in the relational algebra (DL, JVdB), pp. 76–83.
ITiCSE-2005-Christensen05a #architecture #java #named: TS-05: 150 lines of java with high architectural complexity (HBC), p. 396.
ITiCSE-2005-Hovis #programming: Managing the complexity in first year programming (RAH), p. 394.
CSMR-2005-CapiluppiFR #cumulative #open source: Exploring the Relationship between Cumulative Change and Complexity in an Open Source System (AC, AEF, JFR), pp. 21–29.
CIAA-J-2004-JirasekJS05: State complexity of concatenation and complementation (JJ, GJ, AS), pp. 511–529.
CIAA-J-2004-KrawetzLS05 #finite #monad #set: State complexity and the monoid of transformations of a finite set (BK, JL, JS), pp. 547–563.
DLT-J-2004-Lohrey05 #automation #decidability #monad: Decidability and complexity in automatic monoids (ML), pp. 707–722.
DLT-2005-AblayevG #automaton #quantum: Complexity of Quantum Uniform and Nonuniform Automata (FMA, AG), pp. 78–87.
ICALP-2005-AbdullaDOW #automaton #decidability: Decidability and Complexity Results for Timed Automata via Channel Machines (PAA, JD, JO, JW), pp. 1089–1101.
ICALP-2005-BeamePS #bound #communication #multi: Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity (PB, TP, NS), pp. 1176–1188.
ICALP-2005-ChatterjeeAH #game studies #probability: The Complexity of Stochastic Rabin and Streett Games (KC, LdA, TAH), pp. 878–890.
ICALP-2005-FordG #bound #communication #multi: Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity (JF, AG), pp. 1163–1175.
ICALP-2005-KoiranNP #bound #problem #quantum #query: A Quantum Lower Bound for the Query Complexity of Simon’s Problem (PK, VN, NP), pp. 1287–1298.
ICALP-2005-MagniezN #commutative #quantum #testing: Quantum Complexity of Testing Group Commutativity (FM, AN), pp. 1312–1324.
ICALP-2005-PatrascuP #on the: On Dynamic Bit-Probe Complexity (CEP, MP), pp. 969–981.
ICALP-2005-TessonT #communication #strict: Restricted Two-Variable Sentences, Circuits and Communication Complexity (PT, DT), pp. 526–538.
CIKM-2005-GrecoS #consistency #integration #on the #peer-to-peer #query: On the complexity of computing peer agreements for consistent query answering in peer-to-peer data integration systems (GG, FS), pp. 36–43.
CIKM-2005-MasonL #named #query #relational #sql: INFER: a relational query language without the complexity of SQL (TM, RL), pp. 241–242.
KDD-2005-Barabasi #architecture #network #web: The architecture of complexity: the structure and the dynamics of networks, from the web to the cell (ALB), p. 3.
SAC-2005-HuP #3d #parametricity: Volume fractal dimensionality: a useful parameter for measuring the complexity of 3D protein spatial structures (MH, QP), pp. 172–176.
SAC-2005-ZhouX #approach #diagrams: Measuring structural complexity for class diagrams: an information theory approach (YZ, BX), pp. 1679–1683.
DATE-2005-TangWD #power management #synthesis: MINLP Based Topology Synthesis for Delta Sigma Modulators Optimized for Signal Path Complexity, Sensitivity and Power Consumption (HT, YW, AD), pp. 264–269.
DATE-2005-VanderperrenD #approach #design #uml: UML 2 and SysML: An Approach to Deal with Complexity in SoC/NoC Design (YV, WD), pp. 716–717.
ESOP-2005-NiehrenPS #satisfiability #type system: Complexity of Subtype Satisfiability over Posets (JN, TP, ZS), pp. 357–373.
FoSSaCS-2005-BontempsS #sequence chart: The Complexity of Live Sequence Charts (YB, PYS), pp. 364–378.
STOC-2005-Aaronson: The complexity of agreement (SA), pp. 634–643.
STOC-2005-Ben-SassonS #query: Simple PCPs with poly-log rate and query complexity (EBS, MS), pp. 266–275.
STOC-2005-GafniGP #adaptation #bound #set: From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement (EG, RG, BP), pp. 714–722.
STOC-2005-SanghviV #random: The round complexity of two-party random selection (SS, SPV), pp. 338–347.
STOC-2005-Shi #communication #metric #quantum: Tensor norms and the classical communication complexity of nonlocal quantum measurement (YS), pp. 460–467.
SAT-J-2004-BaulandCCHV05 #algebra #approach #query: An Algebraic Approach to the Complexity of Generalized Conjunctive Queries (MB, PC, NC, MH, HV), pp. 30–45.
CADE-2005-VermaSS #equation #horn clause #on the: On the Complexity of Equational Horn Clauses (KNV, HS, TS), pp. 337–352.
CSL-2005-BradfieldK #fixpoint #logic: The Complexity of Independence-Friendly Fixpoint Logic (JCB, SK), pp. 355–368.
CSL-2005-CateF #hybrid #logic #on the: On the Complexity of Hybrid Logics with Binders (BtC, MF), pp. 339–354.
CSL-2005-Lambov #analysis #framework: Complexity and Intensionality in a Type-1 Framework for Computable Analysis (BL), pp. 442–461.
VMCAI-2005-KumarKV #fault #on the: On the Complexity of Error Explanation (NK, VK, MV), pp. 448–464.
PODS-2004-Calders #satisfiability: Computational Complexity of Itemset Frequency Satisfiability (TC), pp. 143–154.
PODS-2004-MeyersonW #on the: On the Complexity of Optimal K-Anonymity (AM, RW), pp. 223–228.
VLDB-2004-SismanisR: The Complexity of Fully Materialized Coalesced Cubes (YS, NR), pp. 540–551.
ICSM-2004-MerloAPR #analysis #clone detection #detection #evolution #linear #object-oriented #similarity: Linear Complexity Object-Oriented Similarity for Clone Detection and Software Evolution Analyses (EM, GA, MDP, VFR), pp. 412–416.
ICSM-2004-MohanGL #approach #comprehension #concept #using: An Approach to Understanding Program Comprehensibility Using Spatial Complexity, Concept Assignment and Typographical Style (AM, NG, PJL), p. 530.
WCRE-2004-MohanGL #approach #concept #using: An Initial Approach to Assessing Program Comprehensibility Using Spatial Complexity, Number of Concepts and Typographical Style (AM, NG, PJL), pp. 246–255.
CIAA-2004-BerstelC #algorithm #on the: On the Complexity of Hopcroft’s State Minimization Algorithm (JB, OC), pp. 35–44.
CIAA-2004-DaleyM #verification: Viral Gene Compression: Complexity and Verification (MD, IM), pp. 102–112.
CIAA-2004-EramianD #question: Does Hausdorff Dimension Measure Texture Complexity? (MGE, MD), pp. 317–318.
CIAA-2004-JirasekJS #regular expression: State Complexity of Concatenation and Complementation of Regular Languages (JJ, GJ, AS), pp. 178–189.
CIAA-2004-KrawetzLS #finite #monad #set: State Complexity and the Monoid of Transformations of a Finite Set (BK, JL, JS), pp. 213–224.
DLT-2004-DowneyM: Some New Directions and Questions in Parameterized Complexity (RGD, CM), pp. 12–26.
DLT-2004-JurdzinskiOMP #automaton #on the: On the Complexity of 2-Monotone Restarting Automata (TJ, FO, FM, MP), pp. 237–248.
DLT-2004-Lohrey #automation #decidability #monad: Decidability and Complexity in Automatic Monoids (ML), pp. 308–320.
ICALP-2004-BulatovG: The Complexity of Partition Functions (AAB, MG), pp. 294–306.
ICALP-2004-Cheney #unification: The Complexity of Equivariant Unification (JC), pp. 332–344.
ICALP-2004-DurrHHM #graph #problem #quantum #query: Quantum Query Complexity of Some Graph Problems (CD, MH, PH, MM), pp. 481–493.
ICALP-2004-KrauthgamerL #black box #nearest neighbour: The Black-Box Complexity of Nearest Neighbor Search (RK, JRL), pp. 858–869.
ICALP-2004-Lyngso #modelling #predict #pseudo: Complexity of Pseudoknot Prediction in Simple Models (RBL), pp. 919–931.
ICALP-2004-Serre #game studies: Games with Winning Conditions of High Borel Complexity (OS), pp. 1150–1162.
ICEIS-v1-2004-Maciaszek #enterprise #information management: Managing Complexity of Enterprise Information Systems (LAM), p. IX-XIII.
ICEIS-v3-2004-Nobre #design #learning: Organisational Learning — Foundational Roots for Design for Complexity (ÂLN), pp. 85–93.
ECIR-2004-BellR #web: Searcher’s Assessments of Task Complexity for Web Searching (DJB, IR), pp. 57–71.
ICML-2004-ConitzerS #bound #communication #game studies #learning: Communication complexity as a lower bound for learning in games (VC, TS).
KDD-2004-Yang #mining: The complexity of mining maximal frequent itemsets and maximal frequent patterns (GY), pp. 344–353.
KR-2004-EiterFFPW #bound #model checking #programming #set: Complexity of Model Checking and Bounded Predicate Arities for Non-ground Answer Set Programming (TE, WF, MF, GP, SW), pp. 377–387.
KR-2004-Provan #abduction #modelling: Inferential Complexity Control for Model-Based Abduction (GMP), pp. 415–426.
ICSE-2004-Lieberherr #design: Controlling the Complexity of Software Design (KJL), pp. 2–11.
STOC-2004-Bar-YossefJK #communication #exponential #quantum: Exponential separation of quantum and classical one-way communication complexity (ZBY, TSJ, IK), pp. 128–137.
STOC-2004-BurgisserC #algebra #set: Counting complexity classes for numeric computations II: algebraic and semialgebraic sets (PB, FC), pp. 475–485.
STOC-2004-FabrikantPT #nash: The complexity of pure Nash equilibria (AF, CHP, KT), pp. 604–612.
CSL-2004-Atserias #random #satisfiability: Notions of Average-Case Complexity for Random 3-SAT (AA), pp. 1–5.
LICS-2004-NordhJ #algebra #approach: An Algebraic Approach to the Complexity of Propositional Circumscription (GN, PJ), pp. 367–376.
SAT-2004-BaulandCCHV #algebra #approach #query: An Algebraic Approach to the Complexity of Generalized Conjunctive Queries (MB, PC, NC, MH, HV), pp. 181–190.
VMCAI-2004-ClarkeKOS #bound #model checking: Completeness and Complexity of Bounded Model Checking (EMC, DK, JO, OS), pp. 85–96.
PODS-2003-CaliLR #consistency #database #decidability #on the #query #semistructured data: On the decidability and complexity of query answering over inconsistent and incomplete databases (AC, DL, RR), pp. 260–271.
PODS-2003-GottlobKP #evaluation #query #xpath: The complexity of XPath query evaluation (GG, CK, RP), pp. 179–190.
PODS-2003-Segoufin #bound #documentation #query #type system #xml: Typing and querying XML documents: some complexity bounds (LS), pp. 167–178.
IWPC-2003-RillingK #comprehension #identification #metric #slicing #using: Identifying Comprehension Bottlenecks Using Program Slicing and Cognitive Complexity Metric (JR, TK), pp. 115–124.
CIAA-2003-GuingneKN #automaton: Running Time Complexity of Printing an Acyclic Automaton (FG, AK, FN), pp. 131–140.
CIAA-2003-Trakhtman #testing: Reducing the Time Complexity of Testing for Local Threshold Testability (AT), pp. 141–149.
CIAA-2003-XieLD #equation #linear #problem #using: New Complexity Results for Some Linear Counting Problems Using Minimal Solutions to Linear Diophantine Equations (GX, CL, ZD), pp. 163–175.
DLT-2003-Vollmer: Complexity Theory Made Easy (HV), pp. 95–110.
ICALP-2003-ChenKPSX #graph #problem: Genus Characterizes the Complexity of Graph Problems: Some Tight Results (JC, IAK, LP, ES, GX), pp. 845–856.
ICALP-2003-FialaP #problem: The Computational Complexity of the Role Assignment Problem (JF, DP), pp. 817–828.
ICALP-2003-GalM #data type: The Cell Probe Complexity of Succinct Data Structures (AG, PBM), pp. 332–344.
ICALP-2003-HallHS #algorithm #multi #performance: Multicommodity Flows over Time: Efficient Algorithms and Complexity (AH, SH, MS), pp. 397–409.
ICALP-2003-HitchcockLM: Scaled Dimension and Nonuniform Complexity (JMH, JHL, EM), pp. 278–290.
ICALP-2003-JainRS #communication #theorem: A Direct Sum Theorem in Communication Complexity via Message Compression (RJ, JR, PS), pp. 300–315.
RTA-2003-SalvatiG #higher-order #linear #on the #λ-calculus: On the Complexity of Higher-Order Matching in the Linear λ-Calculus (SS, PdG), pp. 234–245.
VISSOFT-2003-Hamou-LhadjL #execution #object-oriented: Techniques for Reducing the Complexity of Object-Oriented Execution Traces (AHL, TCL), pp. 35–40.
CAiSE-2003-GeneroP #diagrams #metric #uml: No-redundant Metrics for UML Class Diagram Structural Complexity (MEM, MG, MP), pp. 127–142.
ICEIS-v3-2003-HawryszkiewyczG #process: Managing the Complexity of Emergent Processes (IH, SG), pp. 319–325.
CIKM-2003-YangRK #on the #web: On the complexity of schema inference from web pages in the presence of nullable data attributes (GY, IVR, MK), pp. 224–231.
MLDM-2003-KostersPP #analysis #implementation: Complexity Analysis of Depth First and FP-Growth Implementations of APRIORI (WAK, WP, VP), pp. 284–292.
POPL-2003-Chakaravarthy #analysis: New results on the computability and complexity of points — to analysis (VTC), pp. 115–125.
SAS-2003-FieldGRY #abstraction #type system #verification: Typestate Verification: Abstraction Techniques and Complexity Results (JF, DG, GR, EY), pp. 439–462.
DAC-2003-KiranJRN #behaviour #communication #effectiveness #modelling: A complexity effective communication model for behavioral modeling of signal processing applications (MNVSK, MNJ, PR, SKN), pp. 412–415.
STOC-2003-Gurvits #problem #quantum: Classical deterministic complexity of Edmonds’ Problem and quantum entanglement (LG), pp. 10–19.
STOC-2003-JayramKS: Two applications of information complexity (TSJ, RK, DS), pp. 673–682.
STOC-2003-RettingerW #set: The computational complexity of some julia sets (RR, KW), pp. 177–185.
CADE-2003-LutzST #finite #logic #reasoning: The Complexity of Finite Model Reasoning in Description Logics (CL, US, LT), pp. 60–74.
CSL-2003-BornerBJK #algorithm #constraints #quantifier: Quantified Constraints: Algorithms and Complexity (FB, AAB, PJ, AAK), pp. 58–70.
CSL-2003-DantchevR #on the: On Relativisation and Complexity Gap (SSD, SR), pp. 142–154.
CSL-2003-Gerhardy #analysis: Refined Complexity Analysis of Cut Elimination (PG), pp. 212–225.
CSL-2003-HitchcockLT: The Arithmetical Complexity of Dimension and Randomness (JMH, JHL, ST), pp. 241–254.
CSL-2003-KahlerW #ltl #model checking: Program Complexity of Dynamic LTL Model Checking (DK, TW), pp. 271–284.
CSL-2003-KolaitisP #game studies #on the: On the Complexity of Existential Pebble Games (PGK, JP), pp. 314–329.
CSL-2003-MaksimovaV #calculus #problem: Complexity of Some Problems in Modal and Intuitionistic Calculi (LM, AV), pp. 397–412.
ICLP-2003-WuPR #logic programming #on the: On the Complexity of Dependent And-Parallelism in Logic Programming (YW, EP, DR), pp. 361–376.
LICS-2003-Buresh-OppenheimP: The Complexity of Resolution Refinements (JBO, TP), p. 138–?.
VMCAI-2003-BraghinCFLP #analysis #mobile: Complexity of Nesting Analysis in Mobile Ambients (CB, AC, RF, FLL, CP), pp. 86–101.
PODS-2002-ChatterjiEGY #approximate #on the #optimisation #query: On the Complexity of Approximate Query Optimization (SC, SSKE, SG, MDY), pp. 282–292.
ICSM-2002-Tran-CaoLA #effectiveness #functional #metric #towards: Measuring Software Functional Size: Towards an Effective Measurement of Complexity (DTC, GL, AA), pp. 370–376.
ICSM-2002-WilkieH #object-oriented #tool support: Tool Support for Measuring Complexity in Heterogeneous Object-Oriented Software (FGW, TJH), pp. 152–161.
CIAA-J-2000-PighizziniS02: Unary Language Operations, State Complexity and Jacobsthal’s Function (GP, JS), pp. 145–159.
CIAA-2002-HolzerK #automaton #finite #nondeterminism: State Complexity of Basic Operations on Nondeterministic Finite Automata (MH, MK), pp. 148–157.
DLT-2002-Cassaigne #infinity #word: Constructing Infinite Words of Intermediate Complexity (JC), pp. 173–184.
DLT-2002-DassowNR #on the: On the Descriptional Complexity of Some Variants of Lindenmayer Systems (JD, TYN, BR), pp. 128–139.
DLT-2002-HolzerK #nondeterminism: Unary Language Operations and Their Nondeterministic State Complexity (MH, MK), pp. 162–172.
ICALP-2002-EstebanGM #bound #on the: On the Complexity of Resolution with Bounded Conjunctions (JLE, NG, JM), pp. 220–231.
ICALP-2002-FotakisKKMS #game studies #nash: The Structure and Complexity of Nash Equilibria for a Selfish Routing Game (DF, SCK, EK, MM, PGS), pp. 123–134.
ICALP-2002-HitchcockL #strict #why: Why Computational Complexity Requires Stricter Martingales (JMH, JHL), pp. 549–560.
ICALP-2002-Marathe #predict #towards: Towards a Predictive Computational Complexity Theory (MVM), pp. 22–31.
ICALP-2002-Nisan #approximate #communication #set: The Communication Complexity of Approximate Set Packing and Covering (NN), pp. 868–875.
VISSOFT-2002-RillingSB #analysis #concept #source code #visualisation: The CONCEPT Project — Applying Source Code Analysis to Reduce Information Complexity of Static and Dynamic Visualization Techniques (JR, AS, CB), p. 90.
CAiSE-2002-IvanDP #approach #design #middleware #protocol #using: Managing Complexity of Designing Routing Protocols Using a Middleware Approach (CI, VD, KP), pp. 737–741.
ICPR-v1-2002-WangQ #recognition #using: Face Recognition Using Optimal Non-Orthogonal Wavelet Basis Evaluated by Information Complexity (XW, HQ), pp. 164–167.
ICPR-v2-2002-AnconaCSD #detection #image #parametricity #runtime: Object Detection in Images: Run-Time Complexity and Parameter Selection of Support Vector Machines (NA, GC, ES, AD), pp. 426–429.
ICPR-v2-2002-RidderPD #classification #fault: The Economics of Classification: Error vs. Complexity (DdR, EP, RPWD), pp. 244–247.
KR-2002-BaralZ #model checking: The Complexity of Model Checking for Knowledge Update (CB, YZ), pp. 82–96.
KR-2002-BeygelzimerR #learning #network: Inference Complexity as a Model-Selection Criterion for Learning Bayesian Networks (AB, IR), pp. 558–567.
KR-2002-Coste-MarquisM: Complexity Results for Paraconsistent Inference Relations (SCM, PM), pp. 61–72.
KR-2002-EiterL #approach: Complexity Results for Explanations in the Structural-Model Approach (TE, TL), pp. 49–60.
KR-2002-Fruhwirth #analysis #automation: As Time Goes by: Automatic Complexity Analysis of Simplified Rules (TWF), pp. 547–557.
KR-2002-KoniecznyLM #distance #framework: Distance Based Merging: A General Framework and some Complexity Results (SK, JL, PM), pp. 97–108.
SEKE-2002-Ginige #development #web: Web engineering: managing the complexity of web systems development (AG), pp. 721–729.
DATE-2002-Man #integration #on the: On Nanoscale Integration and Gigascale Complexity in the Post.Com World (HDM), p. 12.
ESOP-2002-NielsonNS #analysis #automation: Automatic Complexity Analysis (FN, HRN, HS), pp. 243–261.
STOC-2002-BatuDKR #approximate: The complexity of approximating entropy (TB, SD, RK, RR), pp. 678–687.
STOC-2002-BeameV #communication #multi #nearest neighbour #problem #trade-off: Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems (PB, EV), pp. 688–697.
STOC-2002-CharikarLLPPRSS #approximate #modelling: Approximating the smallest grammar: Kolmogorov complexity in natural models (MC, EL, DL, RP, MP, AR, AS, AS), pp. 792–801.
STOC-2002-DengPS #on the: On the complexity of equilibria (XD, CHP, SS), pp. 67–71.
STOC-2002-Feige #approximate: Relations between average case complexity and approximation complexity (UF), pp. 534–543.
STOC-2002-GoldbergKP #random: The complexity of choosing an H-colouring (nearly) uniformly at random (LAG, SK, MP), pp. 53–62.
STOC-2002-Raz #matrix #on the: On the complexity of matrix product (RR), pp. 144–151.
STOC-2002-Sivakumar #algorithm: Algorithmic derandomization via complexity theory (DS), pp. 619–626.
CADE-2002-KupfermanSV #calculus: The Complexity of the Graded µ-Calculus (OK, US, MYV), pp. 423–437.
CSL-2002-Leivant: Implicit Computational Complexity for Higher Type Functionals (DL), pp. 367–381.
CSL-2002-MarcinkowskiT #bound #game studies #ltl: Optimal Complexity Bounds for Positive LTL Games (JM, TT), pp. 262–275.
LICS-2002-Cook #proving: Complexity Classes, Propositional Proof Systems, and Formal Theories (SAC), p. 311.
LICS-2002-FrickG #first-order #higher-order #logic #monad #revisited: The Complexity of First-Order and Monadic Second-Order Logic Revisited (MF, MG), pp. 215–224.
LICS-2002-HesseI #problem: Complete Problems for Dynamic Complexity Classes (WH, NI), p. 313–?.
LICS-2002-SoltysC #algebra #linear #proving: The Proof Complexity of Linear Algebra (MS, SAC), pp. 335–344.
SAT-2002-BueningX #morphism #satisfiability: The complexity of homomorphisms and renamings of minimal unsatisfiable formulas (HKB, DX), p. 9.
PODS-2001-CaiCKN #on the: On the Complexity of Join Predicates (JyC, VTC, RK, JFN).
PODS-2001-Grohe #database #query: The Parameterized Complexity of Database Queries (MG), pp. 82–92.
DLT-2001-Lischke: The Root of a Language and Its Complexity (GL), pp. 272–280.
DLT-2001-Razborov #proving: Proof Complexity of Pigeonhole Principles (AAR), pp. 100–116.
ICALP-2001-AlberFN #exponential #graph #problem: Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems (JA, HF, RN), pp. 261–272.
ICALP-2001-BrodalFPO #using: The Complexity of Constructing Evolutionary Trees Using Experiments (GSB, RF, CNSP, AÖ), pp. 140–151.
ICALP-2001-ChakrabartiK #bound #graph #random: Improved Lower Bounds on the Randomized Complexity of Graph Properties (AC, SK), pp. 285–296.
ICALP-2001-HemaspaandraKW: The Complexity of Computing the Size of an Interval (LAH, SK, KWW), pp. 1040–1051.
RTA-2001-Lohrey #automaton #on the #parallel: On the Parallel Complexity of Tree Automata (ML), pp. 201–215.
TLCA-2001-Hofmann #behaviour #bound #memory management #type system #using: From Bounded Arithmetic to Memory Management: Use of Type Theory to Capture Complexity Classes and Space Behaviour (MH0), pp. 2–3.
TLCA-2001-Schubert #order: The Complexity of β-Reduction in Low Orders (AS), pp. 400–414.
QAPL-2001-Fruhwirth #analysis #automation #concurrent #source code: As Time Goes By II: More Automatic Complexity Analysis of Concurrent Rule Programs (TWF), pp. 185–206.
DAC-2001-GizdarskiF #framework #learning: A Framework for Low Complexity Static Learning (EG, HF), pp. 546–549.
DATE-2001-NeauMR #using: Low complexity FIR filters using factorization of perturbed coefficients (CN, KM, KR), pp. 268–272.
ESOP-2001-Muller-OlmR #constant #on the: On the Complexity of Constant Propagation (MMO, OR), pp. 190–205.
FoSSaCS-2001-CharatonikDGMT #mobile #model checking: The Complexity of Model Checking Mobile Ambients (WC, SDZ, ADG, SM, JMT), pp. 152–167.
FoSSaCS-2001-KingKV #automaton #on the #word: On the Complexity of Parity Word Automata (VK, OK, MYV), pp. 276–286.
STOC-2001-AchlioptasBM #proving: A sharp threshold in proof complexity (DA, PB, MSOM), pp. 337–346.
STOC-2001-AraiPU: The complexity of analytic tableaux (NHA, TP, AU), pp. 356–363.
STOC-2001-BulatovKJ #constraints: The complexity of maximal constraint languages (AAB, AAK, PJ), pp. 667–674.
STOC-2001-GennaroIKR #multi: The round complexity of verifiable secret sharing and secure multicast (RG, YI, EK, TR), pp. 580–589.
STOC-2001-IckingM #3d #bound #diagrams #distance: A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D (CI, LM), pp. 316–321.
STOC-2001-KlauckNTZ #communication #interactive #quantum #set: Interaction in quantum communication and the complexity of set disjointness (HK, AN, ATS, DZ), pp. 124–133.
STOC-2001-Pagh #on the: On the cell probe complexity of membership and perfect hashing (RP), pp. 425–432.
STOC-2001-Yao: Some perspective on computational complexity (ACCY), p. 600.
CSL-2001-ChenS: Capture Complexity by Partition (YC, ES), pp. 84–98.
ICLP-2001-LoncT #logic programming #parametricity #semantics #source code: Fixed-Parameter Complexity of Semantics for Logic Programs (ZL, MT), pp. 197–211.
IJCAR-2001-LynchM #decidability #equation #linear: Decidability and Complexity of Finitely Closable Linear Equational Theories (CL, BM), pp. 499–513.
LICS-2001-KirousisK: A Dichotomy in the Complexity of Propositional Circumscription (LMK, PGK), pp. 71–80.
SAT-2001-HuntMS #constraints #probability #problem #quantifier: Complexity and Approximability of Quantified and Stochastic Constraint Satisfaction Problems (HBHI, MVM, RES), pp. 217–230.
PODS-2000-DantsinV #query: Expressive Power and Data Complexity of Query Languages for Trees and Lists (ED, AV), pp. 157–165.
CIAA-2000-Pighizzini: Unary Language Concatenation and Its State Complexity (GP), pp. 252–262.
CIAA-2000-Shallit: State Complexity and Jacobsthal’s Function (JS), pp. 272–278.
CIAA-2000-Wareham #automaton #composition #finite #set: The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata (TW), pp. 302–310.
ICALP-2000-Mayr #bisimulation #on the #parallel #problem #process: On the Complexity of Bisimulation Problems for Basic Parallel Processes (RM), pp. 329–341.
WLC-2000-AvgustinovichFF #infinity #word: Arithmetical Complexity of Infinite Words (SVA, DFDF, AEF), pp. 51–62.
ICPR-v2-2000-HoB #classification #problem: Measuring the Complexity of Classification Problems (TKH, MB), pp. 2043–2047.
ICPR-v2-2000-KeglKN #classification #learning #network: Radial Basis Function Networks and Complexity Regularization in Function Learning and Classification (BK, AK, HN), pp. 2081–2086.
KR-2000-EiterL #knowledge base #reasoning: Complexity Results for Default Reasoning from Conditional Knowledge Bases (TE, TL), pp. 62–73.
KR-2000-MorrisM #on the #reasoning: On the complexity of reasoning about repeating events (RAM, PHM), pp. 580–588.
POPL-2000-MuthD #analysis #data flow #on the: On the Complexity of Flow-Sensitive Dataflow Analyses (RM, SKD), pp. 67–80.
ICRE-2000-NguyenS #modelling #requirements: Essential and Incidental Complexity in Requirements Models (LN, PAS), pp. 130–139.
DAC-2000-JainMMWL #analysis #canonical #composition #graph #how: Analysis of composition complexity and how to obtain smaller canonical graphs (JJ, KM, DM, IW, YL), pp. 681–686.
DATE-2000-SousaA #clustering #fault #modelling #using: Reducing the Complexity of Defect Level Modeling Using the Clustering Effect (JTdS, VDA), pp. 640–644.
STOC-2000-AlekhnovichBRW #calculus: Space complexity in propositional calculus (MA, EBS, AAR, AW), pp. 358–367.
STOC-2000-CramerDD #multi #on the: On the complexity of verifiable secret sharing and multiparty computation (RC, ID, SD), pp. 325–334.
STOC-2000-RothemundW #self: The program-size complexity of self-assembled squares (PWKR, EW), pp. 459–468.
STOC-2000-SamorodnitskyT #query: A PCP characterization of NP with optimal amortized query complexity (AS, LT), pp. 191–199.
STOC-2000-Vadhan #interactive #on the #proving: On transformation of interactive proofs that preserve the prover’s complexity (SPV), pp. 200–207.
CL-2000-BaralTTK: Computational Complexity of Planning Based on Partial Information about the System’s Present and Past States (CB, LCT, RT, VK), pp. 882–896.
CL-2000-DekhtyarDD #constraints #on the: On Complexity of Updates through Integrity Constraints (MID, AJD, SD), pp. 867–881.
CSL-2000-Atserias #bound #fixpoint: The Descriptive Complexity of the Fixed-Points of Bounded Formulas (AA), pp. 172–186.
CSL-2000-Blumensath #bound: Bounded Arithmetic and Descriptive Complexity (AB), pp. 232–246.
CSL-2000-Kuznets #logic #on the: On the Complexity of Explicit Modal Logics (RK), pp. 371–383.
CSL-2000-MakowskyM #combinator #generative #graph #on the: On the Complexity of Combinatorial and Metafinite Generating Functions of Graph Properties in the Computational Model of Blum, Shub and Smale (JAM, KM), pp. 399–410.
LICS-2000-BergmanS #algebra #problem: Computational Complexity of Some Problems Involving Congruences on Algebras (CB, GS), pp. 168–174.
LICS-2000-Fagin #game studies #logic: Logic, Complexity, and Games (RF), p. 3.
PODS-1999-Cosmadakis #query #recursion: Inherent Complexity of Recursive Queries (SSC), pp. 148–154.
PODS-1999-KarloffM #on the #problem: On the Complexity of the View-Selection Problem (HJK, MM), pp. 167–173.
ITiCSE-1999-SternSN #algorithm #animation: A strategy for managing content complexity in algorithm animation (LS, HS, LN), pp. 127–130.
DLT-1999-Cassaigne: Subword complexity and periodicity in two or more dimensions (JC), pp. 14–21.
DLT-1999-KarhumakiP #on the #order #string: On the complexity of computing the order of repetition of a string (JK, WP), pp. 178–184.
ICALP-1999-JiangLV: Average-Case Complexity of Shellsort (TJ, ML, PMBV), pp. 453–462.
ICALP-1999-PelegR #distributed: A Variant of the Arrow Distributed Directory with Low Average Complexity (DP, ER), pp. 615–624.
ICALP-1999-Umans #on the #problem: On the Complexity and Inapproximability of Shortest Implicant Problems (CU), pp. 687–696.
WIA-1999-CampeanuCSY #finite: State Complexity of Basic Operations on Finite Languages (CC, KCI, KS, SY), pp. 60–70.
TLCA-1999-BaillotP #geometry #interactive: Elementary Complexity and Geometry of Interaction (PB, MP), pp. 25–39.
HCI-CCAD-1999-Rebstock #case study #industrial #lessons learnt: Adding complexity to the electronic market model: lessons learned from an oil industry case study (MR), pp. 1147–1151.
SAS-1999-McAllester #analysis #on the: On the Complexity Analysis of Static Analyses (DAM), pp. 312–329.
DAC-1999-DaemsGS #analysis #reduction: Circuit Complexity Reduction for Symbolic Analysis of Analog Integrated Circuits (WD, GGEG, WMCS), pp. 958–963.
DATE-1999-Junkkari #challenge #design #development #testing: Higher Product Complexity and Shorter Development Time — Continuous Challenge to Design and Test Environment (JJ), pp. 2–3.
STOC-1999-BlomerS #independence #on the: On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice (JB, JPS), pp. 711–720.
STOC-1999-ChakrabartiCGL #approximate #bound #nearest neighbour: A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube (AC, BC, BG, AL), pp. 305–311.
STOC-1999-DinitzMR #symmetry: Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (YD, SM, SR), pp. 265–274.
STOC-1999-FederHKM #graph #problem: Complexity of Graph Partition Problems (TF, PH, SK, RM), pp. 464–472.
STOC-1999-NayakW #approximate #quantum #query #statistics: The Quantum Query Complexity of Approximating the Median and Related Statistics (AN, FW), pp. 384–393.
STOC-1999-PanC #matrix #problem: The Complexity of the Matrix Eigenproblem (VYP, ZQC), pp. 507–516.
STOC-1999-PonzioRV #communication #pointer: The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling (SP, JR, SV), pp. 602–611.
STOC-1999-Raz #communication #exponential #quantum: Exponential Separation of Quantum and Classical Communication Complexity (RR), pp. 358–367.
STOC-1999-Rojas #geometry #on the: On the Complexity of Diophantine Geometry in Low Dimensions (JMR), pp. 527–536.
STOC-1999-Servedio #learning: Computational Sample Complexity and Attribute-Efficient Learning (RAS), pp. 701–710.
CADE-1999-Sofronie-Stokkermans #decidability #on the: On the Universal Theory of Varieties of Distributive Lattices with Operators: Some Decidability and Complexity Results (VSS), pp. 157–171.
CADE-1999-Wierzbicki #higher-order: Complexity of the higher order matching (TW), pp. 82–96.
CSL-1999-ArecesBM #hybrid #logic: A Road-Map on Complexity for Hybrid Logics (CA, PB, MM), pp. 307–321.
CSL-1999-GradelK #constraints #database: Descriptive Complexity Theory for Constraint Databases (EG, SK), pp. 67–81.
CSL-1999-Grohe: Descriptive and Parameterized Complexity (MG), pp. 14–31.
CSL-1999-Leivant: Applicative Control and Computational Complexity (DL), pp. 82–95.
LICS-1999-Friedman #problem: Some Decision Problems of Enormous Complexity (HF), pp. 2–12.
LICS-1999-GottlobP #modelling: Working with Arms: Complexity Results on Atomic Representations of Herbrand Models (GG, RP), pp. 306–315.
PODS-1998-AbiteboulD #query #using: Complexity of Answering Queries Using Materialized Views (SA, OMD), pp. 254–263.
PODS-1998-GradelGH #query #reliability: The Complexity of Query Reliability (EG, YG, CH), pp. 227–234.
PODS-1998-KolaitisMT #on the #problem #query: On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates (PGK, DLM, MNT), pp. 197–204.
PODS-1998-VorobyovV #logic programming #recursion #source code: Complexity of Nonrecursive Logic Programs with Complex Values (SGV, AV), pp. 244–253.
CSMR-1998-KazmanB #architecture: Assessing Architectural Complexity (RK, MB), pp. 104–112.
ICALP-1998-AkutsuY #biology #on the #problem: On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology (TA, MY), pp. 832–843.
ICALP-1998-HengleinR #automaton #constraints #recursion #type system: Constraint Automata and the Complexity of Recursive Subtype Entailment (FH, JR), pp. 616–627.
ICALP-1998-RaymondTT #algebra #approach #communication: An Algebraic Approach to Communication Complexity (JFR, PT, DT), pp. 29–40.
ICALP-1998-Walukiewicz: Difficult Configurations — On the Complexity of LTrL (IW), pp. 140–151.
FM-1998-HutterMRSWBRSS #formal method #named: VSE: Controlling the Complexity in Formal Software Developments (DH, HM, GR, WS, AW, MB, WR, GS, KS), pp. 351–358.
ICFP-1998-MinamideG #on the #runtime: On the Runtime Complexity of Type-Directed Unboxing (YM, JG), pp. 1–12.
TAGT-1998-EhrenfeuchtHHR #graph: Complexity Issues in Switching of Graphs (AE, JH, TH, GR), pp. 59–70.
ICPR-1998-EglinBE #using #visual notation: Printed text featuring using the visual criteria of legibility and complexity (VE, SB, HE), pp. 942–944.
ICPR-1998-SardoK #estimation #using #validation: Model complexity validation for PDF estimation using Gaussian mixtures (LS, JK), pp. 195–197.
KR-1998-CervesatoFM #calculus #model checking #quantifier: The Complexity of Model Checking in Modal Event Calculi with Quantifiers (IC, MF, AM), pp. 368–379.
KR-1998-LangM #independence #logic: Complexity Results for Independence and Definability in Propositional Logic (JL, PM), pp. 356–367.
ECOOP-1998-GilI #analysis #object-oriented #source code: The Complexity of Type Analysis of Object Oriented Programs (JYG, AI), pp. 601–634.
ALP-PLILP-1998-PontelliRG #object-oriented: The Complexity of Late-Binding in Dynamic Object-Oriented Languages (EP, DR, GG), pp. 213–229.
ICSE-1998-HerbslebG #case study #concept #metric: Conceptual Simplicity Meets Organizational Complexity: Case Study of a Corporate Metrics Program (JDH, REG), pp. 271–280.
ESOP-1998-ChatterjeeRL #exception: Complexity of Concrete Type-Inference in the Presence of Exceptions (RC, BGR, WL), pp. 57–74.
STOC-1998-BabaiHK #communication #cost analysis: The Cost of the Missing Bit: Communication Complexity with Help (LB, TPH, PGK), pp. 673–682.
STOC-1998-BeameKPS #on the #proving #random #satisfiability: On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas (PB, RMK, TP, MES), pp. 561–571.
STOC-1998-CrescenziGPPY #on the: On the Complexity of Protein Folding (PC, DG, CHP, AP, MY), pp. 597–603.
STOC-1998-Grigoriev #bound #random: Randomized Complexity Lower Bounds (DG), pp. 219–223.
CSL-1998-BonfanteCMT #polynomial #term rewriting: Complexity Classes and Rewrite Systems with Polynomial Interpretation (GB, AC, JYM, HT), pp. 372–384.
CSL-1998-Pezzoli #finite #game studies: Computational Complexity of Ehrenfeucht-Fraïssé Games on Finite Structures (EP), pp. 159–170.
CSL-1998-Pichler #on the: On the Complexity of H-Subsumption (RP), pp. 355–371.
CSL-1998-RicheM #decidability: Belnap, Urquhart and Relevant Decidability & Complexity. “Das ist nicht Mathematik, das ist Theologie.” (JR, RKM), pp. 224–240.
CSL-1998-Schwentick #bound #linear: Descriptive Complexity, Lower Bounds and Linear Time (TS), pp. 9–28.
ECDL-1997-BernDM #library: The Electronic Colloquium on Computational Complexity (ECCC): A Digital Library in Use (JB, CD, CM), pp. 405–421.
HT-1997-Kolb #hypermedia #self: Scholarly Hypertext: Self-Represented Complexity (DK), pp. 29–37.
PODS-1997-PapadimitriouY #database #on the #query: On the Complexity of Database Queries (CHP, MY), pp. 12–19.
PODS-1997-ScheufeleM #generative #on the: On the Complexity of Generating Optimal Plans with Cross Products (WS, GM), pp. 238–248.
VLDB-1997-PellenkoftLK: The Complexity of Transformation-Based Join Enumeration (AP, CAGL, MLK), pp. 306–315.
DLT-1997-IkedaA #on the: On the Complexity of Languages Definable by Hereditary Elementary Formal Systems (DI, HA), pp. 223–235.
DLT-1997-Moshkov #nondeterminism #recognition #regular expression #word: Complexity of Deterministic and Nondeterministic Decision Trees for Regular Language Word Recognition (MM), pp. 343–349.
ICALP-1997-Ambainis #bound #communication #information retrieval: Upper Bound on Communication Complexity of Private Information Retrieval (AA), pp. 401–407.
ICFP-1997-HeintzeM #analysis #on the: On the Complexity of Set-Based Analysis (NH, DAM), pp. 150–163.
HCI-CC-1997-SavidisS97a #declarative #framework #specification: Agent Classes for Managing Dialogue Control Specification Complexity: A Declarative Language Framework (AS, CS), pp. 461–464.
HCI-SEC-1997-Hollnagel97a #design: Designing for Complexity (EH), pp. 217–220.
ICML-1997-OatesJ #set: The Effects of Training Set Size on Decision Tree Complexity (TO, DJ), pp. 254–262.
POPL-1997-Deutsch #analysis #on the: On the Complexity of Escape Analysis (AD), pp. 358–371.
TRI-Ada-1997-HendrixCBM #ada #visualisation: Visualization of Control Structure and Complexity in Ada 95 (TDH, JHCI, LAB, KSM), pp. 135–139.
RE-1997-ZaveJ #requirements: Requirements for Telecommunications Services: An Attack on Complexity (PZ, MJ), pp. 106–117.
STOC-1997-AgrawalAIPR #reduction: Reducing the Complexity of Reductions (MA, EA, RI, TP, SR), pp. 730–738.
STOC-1997-BelingV #combinator: Combinatorial Complexity of the Central Curve (PAB, SV), pp. 250–255.
STOC-1997-Dietzfelbinger #communication #problem: The Linear-Array Problem in Communication Complexity Resolved (MD), pp. 373–382.
STOC-1997-Vardy #algorithm #distance #problem: Algorithmic Complexity in Coding Theory and the Minimum Distance Problem (AV), pp. 92–109.
TAPSOFT-1997-MuthD #alias #analysis #on the #pointer: On the Complexity of Function Pointer May-Alias Analysis (RM, SKD), pp. 381–392.
CSL-1997-Pezzoli #on the: On the Computational Complexity of Type 2 Functionals (EP), pp. 373–388.
ICLP-1997-CervesatoFM #calculus #model checking: The Complexity of Model Checking in Modal Event Calculi (IC, MF, AM), p. 419.
LICS-1997-HengleinR #type system: The Complexity of Subtype Entailment for Simple Types (FH, JR), pp. 352–361.
LICS-1997-Kozen #algebra #on the #reasoning: On the Complexity of Reasoning in Kleene Algebra (DK), pp. 195–202.
LICS-1997-PacholskiST #logic: Complexity of Two-Variable Logic with Counting (LP, WS, LT), pp. 318–327.
LICS-1997-ZhangR #reasoning: Complexity of Power Default Reasoning (GQZ, WCR), pp. 328–339.
HT-1996-JoyceKMSU #design #generative #problem #visual notation #visualisation #web: Visual Metaphor and the Problem of Complexity in the Design of Web Sites: Techniques for Generating, Recognizing and Visualizing Structure (MJ, RK, SM, BS, JMU), p. 257.
ICSM-1996-TakahashiN #fault #interface: The effect of interface complexity on program error density (RT, YN), pp. 77–86.
ICALP-1996-PatersonP #on the #string: On the Complexity of String Folding (MP, TMP), pp. 658–669.
ICALP-1996-ShuklaHRS #finite #on the #problem #process #relational: On the Complexity of Relational Problems for Finite State Processes (SKS, HBHI, DJR, RES), pp. 466–477.
ICFP-1996-Ghelli #kernel #type checking #type system: Complexity of Kernel Fun Subtype Checking (GG), pp. 134–145.
ICPR-1996-HoK #classification: Building projectable classifiers of arbitrary complexity (TKH, EMK), pp. 880–885.
ICPR-1996-KrzyzakL #classification #convergence #network #parametricity: Radial basis function networks and nonparametric classification: complexity regularization and rates of convergence (AK, TL), pp. 650–653.
ICPR-1996-LeonardisB #adaptation #network #optimisation: Complexity optimization of adaptive RBF networks (TL, HB), pp. 654–658.
ICPR-1996-PeiH96a #algorithm #detection #symmetry: A low complexity algorithm for detecting rotational symmetry based on the Hough transform technique (SCP, JHH), pp. 492–496.
ICPR-1996-SardoK #correlation #estimation: Minimum complexity PDF estimation for correlated data (LS, JK), pp. 750–754.
KR-1996-Gottlob #power of: Complexity and Expressive Power of KR Formalisms (GG), pp. 647–649.
SEKE-1996-Zadrozny #natural language: Natural Language Processing: Structure and Complexity (WZ), pp. 595–602.
POPL-1996-Asperti #on the: On the Complexity of β-Reduction (AA), pp. 110–118.
KBSE-1996-Benner #automation #coordination #development: Addressing Complexity, Coordination, and Automation in Software Development with the KBSA/ADM (KB), p. 13.
STOC-1996-AfekMO #algorithm #convergence: Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (YA, YM, ZO), pp. 89–98.
STOC-1996-AllenderBO #equation #linear #matrix #rank: The Complexity of Matrix Rank and Feasible Systems of Linear Equations (EA, RB, MO), pp. 161–167.
STOC-1996-AlonMS #approximate: The Space Complexity of Approximating the Frequency Moments (NA, YM, MS), pp. 20–29.
STOC-1996-Beaver #correlation #pseudo: Correlated Pseudorandomness and the Complexity of Private Computations (DB), pp. 479–488.
STOC-1996-ChaudhuriR #strict: Deterministic Restrictions in Circuit Complexity (SC, JR), pp. 30–36.
STOC-1996-KushilevitzLO #communication: The Linear-Array Conjecture in Communication Complexity is False (EK, NL, RO), pp. 1–10.
LICS-1996-BasinG #analysis #order: Complexity Analysis Based on Ordered Resolution (DAB, HG), pp. 456–465.
LICS-1996-HirstH #recursion: More About Recursive Structures: Descriptive Complexity and Zero-One Laws (TH, DH), pp. 334–347.
LICS-1996-MarekNR #abduction #on the: On the Complexity of Abduction (VWM, AN, JBR), pp. 513–522.
PODS-1995-Vardi #bound #on the #query: On the Complexity of Bounded-Variable Queries (MYV), pp. 266–276.
ICSM-1995-Schneberger #component #distributed #maintenance: Software maintenance in distributed computer environments: system complexity versus component simplicity (SLS), pp. 304–317.
DLT-1995-Cai #component: The Computational Complexity of PCGS with Regular Components (LC), pp. 209–219.
DLT-1995-Cassaigne #linear #sequence: Special Factors of Sequences with Linear Subword Complexity (JC), pp. 25–34.
DLT-1995-Georgescu #context-free grammar #metric #orthogonal: The Orthogonality of Some Complexity Measures of Context-Free Languages (GG), pp. 73–78.
DLT-1995-Hromkovic #communication #generative #on the: On the Communication Complexity of Distributive Language Generation (JH), pp. 237–246.
DLT-1995-Lepisto #infinity #on the #word: On the Computational Complexity of Infinite Words (AL), pp. 350–359.
ICALP-1995-Balcazar #graph: The Complexity of Searching Succinctly Represented Graphs (JLB), pp. 208–219.
ICML-1995-Niyogi #learning: Free to Choose: Investigating the Sample Complexity of Active Learning of Real Valued Functions (PN), pp. 405–412.
ICML-1995-Schmidhuber: Discovering Solutions with Low Kolmogorov Complexity and High Generalization Capability (JS), pp. 488–496.
KDD-1995-CortesDHV #capacity #predict: Capacity and Complexity Control in Predicting the Spread Between Borrowing and Lending Interest Rates (CC, HD, DH, VV), pp. 51–56.
LOPSTR-1995-Aarts #source code: Complexity of Horn Programs (EA), pp. 76–90.
DAC-1995-StollonP #behaviour #metric #modelling: Measures of Syntactic Complexity for Modeling Behavioral VHDL (NSS, JDP), pp. 684–689.
STOC-1995-BealsNT: More on the complexity of negation-limited circuits (RB, TN, KT), pp. 585–595.
STOC-1995-BeameCEIP #problem: The relative complexity of NP search problems (PB, SAC, JE, RI, TP), pp. 303–314.
STOC-1995-GradelM: Descriptive complexity theory over the real numbers (EG, KM), pp. 315–324.
STOC-1995-KremerNR #communication #on the #random: On randomized one-round communication complexity (IK, NN, DR), pp. 596–605.
STOC-1995-MiltersenNSW #communication #data type #on the #symmetry: On data structures and asymmetric communication complexity (PBM, NN, SS, AW), pp. 103–111.
STOC-1995-NisanW #memory management #on the: On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern (NN, AW), pp. 723–732.
LICS-1995-Kanovich #linear #logic: The Complexity of Neutrals in Linear Logic (MIK), pp. 486–495.
LICS-1995-MarekNR #logic #reasoning: Complexity of Normal Default Logic and Related Modes of Nonmonotonic Reasoning (VWM, AN, JBR), pp. 178–185.
LICS-1995-Seth #fixpoint #logic #question: When Do Fixed Point Logics Capture Complexity Classes? (AS), pp. 353–363.
LICS-1995-Vardi #composition #model checking #on the: On the Complexity of Modular Model Checking (MYV), pp. 101–111.
PODS-1994-ChaudhuriV #datalog #equivalence #on the #recursion #source code: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs (SC, MYV), pp. 107–116.
PODS-1994-PatnaikI #named #parallel: Dyn-FO: A Parallel, Dynamic Complexity Class (SP, NI), pp. 210–221.
ICSM-1994-ChenS #metric #rule-based: Complexity Metrics for Rule-Based Expert Systems (ZC, CYS), pp. 382–391.
ICSM-1994-LanningK #canonical #fault #modelling #process: Canonical Modeling of Software Complexity and Fault Correction Activity (DLL, TMK), pp. 374–381.
ICALP-1994-GlobermanH #automaton #logic #multi: Complexity Results for Multi-Pebble Automata and their Logics (NG, DH), pp. 73–82.
ICALP-1994-GradelG: Tailoring Recursing for Complexity (EG, YG), pp. 118–129.
ICALP-1994-JakobyRSW #parallel #problem: The Average Case Complexity of the Parallel Prefix Problem (AJ, RR, CS, SW), pp. 593–604.
ICALP-1994-Pudlak #bound #communication #game studies: Unexpected Upper Bounds on the Complexity of Some Communication Games (PP), pp. 1–10.
KR-1994-FriedmanH94a #logic #on the: On the Complexity of Conditional Logics (NF, JYH), pp. 202–213.
KR-1994-Koubarakis #constraints #first-order: Complexity Results for First-Order Theories of Temporal Constraints (MK), pp. 379–390.
SEKE-1994-Tovar #information management #metric: Applicability of McCabe’s complexity metric to knowledge engineering products (ET), pp. 508–515.
ICRE-1994-Alford #requirements #using: Attacking requirements complexity using a separation of concerns (MWA), pp. 2–5.
EDAC-1994-BurgunDGPS #logic #multi #synthesis: Multilevel Logic Synthesis of Very High Complexity Circuits (LB, ND, AG, EP, CS), p. 669.
EDAC-1994-GreinerLWW #design #library: Design of a High Complexity Superscalar Microprocessor with the Portable IDPS ASIC Library (AG, LL, FW, LW), pp. 9–13.
STOC-1994-AnderssonHHP #array #string: The complexity of searching a sorted array of strings (AA, TH, JH, OP), pp. 317–325.
STOC-1994-GoldreichOP: Computational complexity and knowledge complexity (OG, RO, EP), pp. 534–543.
STOC-1994-JakobyRS: Circuit complexity: from the worst case to the average case (AJ, RR, CS), pp. 58–67.
STOC-1994-JiangLW #approximate #sequence: Aligning sequences via an evolutionary tree: complexity and approximation (TJ, ELL, LW), pp. 760–769.
STOC-1994-Kurshan #verification: The complexity of verification (RPK), pp. 365–371.
STOC-1994-LiptonY #game studies #scalability: Simple strategies for large zero-sum games with applications to complexity theory (RJL, NEY), pp. 734–740.
STOC-1994-MaG #permutation: The computational complexity of recognizing permutation functions (KM, JvzG), pp. 392–401.
STOC-1994-MuthukrishnanP #algorithm #standard #string: Non-standard stringology: algorithms and complexity (SM, KVP), pp. 770–779.
STOC-1994-PapadimitriouY #bound #on the: On complexity as bounded rationality (CHP, MY), pp. 726–733.
STOC-1994-TanakaN #network #on the: On the complexity of negation-limited Boolean networks (KT, TN), pp. 38–47.
STOC-1994-Yao: Decision tree complexity and Betti numbers (ACCY), pp. 615–624.
CADE-1994-HermannK #equation #problem: The Complexity of Counting Problems in Equational Matching (MH, PGK), pp. 560–574.
ILPS-1994-Gottlob #logic programming #power of: Complexity and Expressive Power of Disjunctive Logic Programming (GG), pp. 23–42.
LICS-1994-Hemaspaandra #logic: Complexity Transfer for Modal Logic (EH), pp. 164–173.
LICS-1994-ZhangSS #calculus #model checking #on the #parallel #μ-calculus: On the Parallel Complexity of Model Checking in the Modal μ-Calculus (SZ, OS, SAS), pp. 154–163.
ICDAR-1993-InoharaKSS #database #retrieval #using: Retrieval method of textile pictures database using a complexity scale (TI, KK, HS, SS), pp. 699–702.
ICDAR-1993-Ishitani #detection #documentation: Document skew detection based on local region complexity (YI), pp. 49–52.
PODS-1993-EiterG #aspect-oriented #database #semantics: Complexity Aspects of Various Semantics for Disjunctive Databases (TE, GG), pp. 158–167.
DLT-1993-DammHLR: Deterministic OL Languages are of Very Low Complexity: DOL is in AC0 (CD, MH, KJL, PR), pp. 305–313.
ICALP-1993-Ablayev #bound #communication #probability: Lower Bounds for One-way Probabilistic Communication Complexity (FMA), pp. 241–252.
ICALP-1993-Hemachandra #fault tolerance: Fault-Tolerance and Complexity (LAH), pp. 189–202.
ICALP-1993-MaratheHR #approximate #problem #specification: The Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications (MVM, HBHI, SSR), pp. 76–87.
ICALP-1993-ReifT #simulation: The Complexity of N-body Simulation (JHR, SRT), pp. 162–176.
HCI-ACS-1993-LawtonML #design #process: Managing Complexity: Display Design in Process Control (GLL, DLM, PLL), pp. 139–144.
HCI-ACS-1993-VankovGRV: Operational Complexity of Controlling Space Vehicles (AV, YG, AR, AV), pp. 219–224.
HCI-ACS-1993-VekkerAY #on the: On Psychophysiology of Cognitive Complexity (LV, JAA, YY), pp. 605–610.
HCI-ACS-1993-VendaH #analysis: Qualitative and Quantitative Analysis of Human Decision-Making Complexity (VFV, HWH), pp. 636–641.
HCI-ACS-1993-YufikS #framework #human-computer #interface: A Framework for Measuring Cognitive Complexity of the Human-Machine Interface (YMY, TBS), pp. 587–592.
HCI-SHI-1993-GlazkovRVV: Control of Cosmonauts Training to Overcome Operational Complexity (YG, AR, AV, AV), pp. 772–777.
SEKE-1993-Cheng #metric #rule-based: A New Complexity Metric for OPS5 Rule-Based Systems (AMKC), pp. 244–247.
PLILP-1993-Dikovsky #prolog: Abstract Complexity of Prolog Based on WAM (AJD), pp. 365–377.
POPL-1993-DhamdhereK #analysis #bidirectional #data flow: Complexity of Bidirectional Data Flow Analysis (DMD, UPK), pp. 397–408.
POPL-1993-Leivant #functional #source code: Stratified Functional Programs and Computational Complexity (DL), pp. 325–333.
SAC-1993-Liu #approach: To Approach an Intelligent System in Coping with an Aspect of Complexity of Water Management (YL), pp. 460–468.
SAC-1993-ONeal #empirical #metric: An Empirical Study of Three Common Software Complexity Measures (MBO), pp. 203–207.
STOC-1993-BernsteinV #quantum: Quantum complexity theory (EB, UVV), pp. 11–20.
STOC-1993-ChouK #2d: Some complexity issues on the simply connected regions of the two-dimensional plane (AWC, KIK), pp. 1–10.
STOC-1993-Maass #bound #learning: Bounds for the computational power and learning complexity of analog neural nets (WM), pp. 335–344.
CSL-1993-AikenKVW #constraints #set: The Complexity of Set Constraints (AA, DK, MYV, ELW), pp. 1–17.
ILPS-1993-EiterG #logic #logic programming: Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics (TE, GG), pp. 266–278.
PODS-1992-Bonner #reuse: The Complexity of Reusing and Modifying Rulebases (AJB), pp. 316–330.
PODS-1992-EiterG #knowledge base #on the: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals (TE, GG), pp. 261–273.
PODS-1992-Meyden #order #query: The Complexity of Querying Indefinite Data about Linearly Ordered Domains (RvdM), pp. 331–345.
ICALP-1992-ChazelleR #bound #pointer: Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine (BC, BR), pp. 439–449.
ICALP-1992-Debray #analysis #data flow #logic programming #on the #source code: On the Complexity of Dataflow Analysis of Logic Programs (SKD), pp. 509–520.
ICALP-1992-LiV: Philosophical Issues in Kolmogorov Complexity (ML, PMBV), pp. 1–15.
ICALP-1992-Straubing #first-order #power of: Circuit Complexity and the Expressive Power of Generalized First-Order Formulas (HS), pp. 16–27.
KR-1992-NiemelaR #on the #reasoning: On the Impact of Stratification on the Complexity of Nonmonotonic Reasoning (IN, JR), pp. 627–638.
POPL-1992-JoungS #interactive #multi: A Comprehensive Study of the Complexity of Multiparty Interaction (YJJ, SAS), pp. 142–153.
STOC-1992-BabaiBT #symmetry: Symmetry and Complexity (LB, RB, PTN), pp. 438–449.
STOC-1992-BeameL #communication #nondeterminism #random: Randomized versus Nondeterministic Communication Complexity (PB, JL), pp. 188–199.
STOC-1992-DahlhausJPSY #multi: The Complexity of Multiway Cuts (ED, DSJ, CHP, PDS, MY), pp. 241–251.
STOC-1992-FranklinY #communication: Communication Complexity of Secure Computation (MKF, MY), pp. 699–710.
STOC-1992-Kelsen #independence #on the #parallel #set: On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph (PK), pp. 339–350.
STOC-1992-SimonS #on the #ram #set: On the Complexity of RAM with Various Operation Sets (JS, MS), pp. 624–631.
CADE-1992-CichonL #algorithm #polynomial: Polynomial Interpretations and the Complexity of Algorithms (AC, PL), pp. 139–147.
LICS-1992-KapurN #set: Double-exponential Complexity of Computing a Complete Set of AC-Unifiers (DK, PN), pp. 11–21.
PODS-1991-Roy #clustering #independence #query #relational #semantics: Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning (SR), pp. 259–267.
ICALP-1991-DiekertOR #confluence #decidability #on the: On Confluent Semi-Commutations — Decidability and Complexity Results (VD, EO, KR), pp. 229–241.
ICALP-1991-Gurevich: Average Case Complexity (YG), pp. 615–628.
FPCA-1991-VolpanoS #ml #on the: On the Complexity of ML Typability with Overloading (DMV, GS), pp. 15–28.
KR-1991-DoniniLNN #concept: The Complexity of Concept Languages (FMD, ML, DN, WN), pp. 151–162.
ML-1991-Whitehead: Complexity and Cooperation in Q-Learning (SDW), pp. 363–367.
POPL-1991-HengleinM #higher-order #type inference #λ-calculus: The Complexity of Type Inference for Higher-Order Typed λ Calculi (FH, HGM), pp. 119–130.
WSA-1991-DornicJG #polymorphism: Polymorphic Time Systems for Estimating Program Complexity (VD, PJ, DKG), pp. 9–17.
CAAP-1991-JonssonL #algebra #equation #on the #process: On the Complexity of Equation Solving in Process Algebra (BJ, KGL), pp. 381–396.
STOC-1991-AbiteboulV: Generic Computation and Its Complexity (SA, VV), pp. 209–219.
STOC-1991-NisanW #communication #revisited: Rounds in Communication Complexity Revisited (NN, AW), pp. 419–429.
CAV-1991-FeigenbaumKL: Complexity Results for POMSET Languages (JF, JAK, CL), pp. 343–353.
CSL-1991-Fernando #bisimulation #logic #recursion #set: A Primitive Recursive Set Theory and AFA: On the Logical Complexity of the Largest Bisimulation (TF), pp. 96–110.
ICLP-1991-CharlierMH #abstract interpretation #algorithm #analysis: A Generic Abstract Interpretation Algorithm and its Complexity Analysis (BLC, KM, PVH), pp. 64–78.
ICLP-1991-DebrayL #analysis #automation #logic programming #source code: Automatic Complexity Analysis of Logic Programs (SKD, NWL), pp. 599–613.
LICS-1991-Hungar #bound #hoare #proving: Complexity Bounds of Hoare-style Proof Systems (HH), pp. 120–126.
SIGMOD-1990-UllmanY #transitive: The Input/Output Complexity of Transitive Closure (JDU, MY), pp. 44–53.
VLDB-1990-OnoL #optimisation #query: Measuring the Complexity of Join Enumeration in Query Optimization (KO, GML), pp. 314–325.
ICALP-1990-Razborov #on the: On the Distributional Complexity of Disjontness (AAR), pp. 249–253.
ML-1990-Valtorta #knowledge base #network #refinement: More Results on the Complexity of Knowledge Base Refinement: Belief Networks (MV), pp. 419–426.
ALP-1990-Li #optimisation: Optimization of Rewriting and Complexity of Rewriting (KL), pp. 359–371.
DAC-1990-ChengA #multi: An Entropy Measure for the Complexity of Multi-Output Boolean Functions (KTC, VDA), pp. 302–305.
ESOP-1990-Sands #analysis #higher-order #lazy evaluation: Complexity Analysis for a Lazy Higher-Order Language (DS), pp. 361–376.
STOC-1990-BeaverMR #protocol: The Round Complexity of Secure Protocols (DB, SM, PR), pp. 503–513.
STOC-1990-BellareMO90a #statistics: The (True) Complexity of Statistical Zero Knowledge (MB, SM, RO), pp. 494–502.
STOC-1990-Lakshman #on the: On the Complexity of Computing a Gröbner Basis for the Radical of a Zero Dimensional Ideal (YNL), pp. 555–563.
STOC-1990-MansourNT: The Computational Complexity of Universal Hashing (YM, NN, PT), pp. 235–243.
STOC-1990-PapadimitriouSY #on the: On the Complexity of Local Search (CHP, AAS, MY), pp. 438–445.
STOC-1990-Szegedy #bound #communication #symmetry: Functions with Bounded Symmetric Communication Complexity and Circuits with mod m Gates (MS), pp. 278–286.
CAV-1990-HamaguchiHY #branch #linear #logic #model checking: Branching Time Regular Temporal Logic for Model Checking with Linear Time Complexity (KH, HH, SY), pp. 253–262.
CSL-1990-BlassG #on the #reduction: On the Reduction Theory for Average Case Complexity (AB, YG), pp. 17–30.
CSL-1990-Mundici #adaptation: The Complexity of Adaptive Error-Correcting Codes (DM), pp. 300–307.
LICS-1990-AlurH #logic #realtime: Real-time Logics: Complexity and Expressiveness (RA, TAH), pp. 390–401.
NACLP-1990-CoxMT #constraints #logic programming #programming language: Computational Complexity and Constraint Logic Programming Languages (JC, KM, CT), pp. 401–415.
PODS-1989-ImielinskiV #database #query: Complexity of Query Processing in Databases with OR-Objects (TI, KVV), pp. 51–65.
SIGMOD-1989-HullS #database #object-oriented #on the #strict: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (RH, JS), pp. 147–158.
ICALP-1989-HochbaumS #optimisation: The Complexity of Nonlinear Separable Optimization (DSH, JGS), pp. 461–472.
ICALP-1989-LiV89a #approach #formal method: A New Approach to Formal Language Theory by Kolmogorov Complexity (ML, PMBV), pp. 506–520.
ICALP-1989-McKenzieT #automaton: Automata Theory Meets Circuit Complexity (PM, DT), pp. 589–602.
ICALP-1989-PruhsM: The Complexity of Controlled Selection (KP, UM), pp. 672–686.
ICALP-1989-Toran #combinator: A Combinatorial Technique for Separating Counting Complexity Classes (JT), pp. 733–744.
RTA-1989-NaoiI #algebra #semantics #term rewriting: Algebraic Semantics and Complexity of Term Rewriting Systems (TN, YI), pp. 311–325.
FPCA-1989-Rosendahl #analysis #automation: Automatic Complexity Analysis (MR), pp. 144–156.
FPCA-1989-WandO #on the #type inference: On the Complexity of Type Inference with Coercion (MW, PO), pp. 293–298.
KR-1989-BylanderATJ #abduction: Some Results Concerning the Computational Complexity of Abduction (TB, DA, MCT, JRJ), pp. 44–54.
ML-1989-Valtorta #knowledge-based #refinement: Some Results on the Complexity of Knowledge-Based Refinement (MV), pp. 326–331.
SEKE-1989-FanH #metric: A Comprehensive Software Complexity Metric for Primitive Modules (ZF, JMH), pp. 67–72.
ICSE-1989-MunsonK: The Dimensionality of Program Complexity (JCM, TMK), pp. 245–253.
ICSE-1989-NakagawaH #fault #metric #reliability: An Error Complexity Model for Software Reliability Measurement (YN, SH), pp. 230–236.
DAC-1989-HwangOI #communication #logic #multi #synthesis #using: Multi-Level Logic Synthesis Using Communication Complexity (TH, RMO, MJI), pp. 215–220.
STOC-1989-AlonBLP #communication #on the: On the Complexity of Radio Communication (NA, ABN, NL, DP), pp. 274–285.
STOC-1989-Ben-DavidCGL #formal method #on the: On the Theory of Average Case Complexity (SBD, BC, OG, ML), pp. 204–216.
STOC-1989-FredmanS #data type: The Cell Probe Complexity of Dynamic Data Structures (MLF, MES), pp. 345–354.
CSL-1989-Dahlhaus #linear: The Complexity of Subtheories of the Existential Linear Theory of Reals (ED), pp. 76–89.
CSL-1989-Gradel #concept #logic #on the: On Logical Descriptions of Some Concepts in Structural Complexity Theory (EG), pp. 163–175.
CSL-1989-SpeckenmeyerK #clustering #on the #set: On the Average Time Complexity of Set Partitioning (ES, RK), pp. 369–381.
CSL-1989-Wette #recursion #representation: Sequential Representation of Primitive Recursive Functions, and Complexity Classes (EW), pp. 422–437.
LICS-1989-Goerdt #recursion: Characterizing Complexity Classes By Higher Type Primitive Recursive Definitions (AG), pp. 364–374.
LICS-1989-Stolboushkin #bound #logic: Some Complexity Bounds for Dynamic Logics (APS), pp. 324–332.
LICS-1989-Vardi #on the #reasoning: On the Complexity of Epistemic Reasoning (MYV), pp. 243–252.
PODS-1988-UllmanV: The Complexity of Ordering Subgoals (JDU, MYV), pp. 74–81.
ICALP-1988-AggarwalC #communication: Communication Complexity of PRAMs (AA, AKC), pp. 1–17.
ICALP-1988-AlbertF #algorithm #analysis #multi: Average Case Complexity Analysis of the Rete Multi-Pattern Match Algorithm (LA, FF), pp. 18–37.
ICALP-1988-DietzfelbingerM #matrix #turing machine: The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines with Output Tape (MD, WM), pp. 188–200.
ICALP-1988-Hartmanis: New Developments in Structural Complexity Theory (JH), pp. 271–286.
ICALP-1988-KruskalRS #algorithm #parallel #performance: A Complexity Theory of Efficient Parallel Algorithms (CPK, LR, MS), pp. 333–346.
ICALP-1988-Watanabe #nondeterminism #on the: On ≤ᴾ₁₋tt-Sparseness and Nondeterministic Complexity Classes (OW0), pp. 697–709.
STOC-1988-HajnalMT #communication #graph #on the: On the Communication Complexity of Graph Properties (AH, WM, GT), pp. 186–191.
STOC-1988-King #bound #graph: Lower Bounds on the Complexity of Graph Properties (VK), pp. 468–476.
STOC-1988-PapadimitriouY88a #approximate #optimisation: Optimization, Approximation, and Complexity Classes (CHP, MY), pp. 229–234.
CSL-1988-Goerdt #recursion: Characterizing Complexity Classes by General Recursive Definitions in Higher Types (AG), pp. 99–117.
CSL-1988-Gradel #modelling #nondeterminism: Size of Models versus Length of Computations: On Inseparability by Nondeterministic Time Complexity Classes (EG), pp. 118–137.
CSL-1988-Karpinski #algebra #problem: Boolean Complexity of Algebraic Interpolation Problems (MK), pp. 138–147.
CSL-1988-Niemela #logic #on the #problem: On the Complexity of the Decision Problem in Propositional Nonmonotonic Logic (IN), pp. 226–239.
CSL-1988-OchozkaSS #logic programming #normalisation #source code: Normal Forms and the Complexity of Computations of Logic Programs (VO, OS, PS), pp. 357–371.
JICSCP-1988-Kaplan88 #algorithm #logic programming #source code: Algorithmic Complexity of Logic Programs (SK), pp. 780–793.
PODS-1987-AfratiP #parallel #query: The Parallel Complexity of Simple Chain Queries (FNA, CHP), pp. 210–213.
PODS-1987-Marchetti-SpaccamelaPS #analysis #implementation #logic #query #worst-case: Worst-case Complexity Analysis of Methods for Logic Query Implementation (AMS, AP, DS), pp. 294–301.
ICALP-1987-AggarwalV #problem #sorting: The I/O Complexity of Sorting and Related Problems (AA, JSV), pp. 467–478.
ICALP-1987-CaiM #graph #on the: On the Complexity of Graph Critical Uncolorability (JyC, GEM), pp. 394–403.
ICALP-1987-LiY #parallel #probability #symmetry: The Probabilistic and Deterministic Parallel Complexity of Symmetric Functions (ML, YY), pp. 326–335.
ICALP-1987-MehlhornNA #bound #problem: A Lower Bound for the Complexity of the Union-Split-Find Problem (KM, SN, HA), pp. 479–488.
ICALP-1987-Muller: Uniform Computational Complexity of Taylor Series (NTM), pp. 435–444.
RTA-1987-Benois #algorithm #automaton #regular expression #term rewriting: Descendants of Regular Language in a Class of Rewriting Systems: Algorithm and Complexity of an Automata Construction (MB), pp. 121–132.
RTA-1987-ChoppyKS #algorithm #term rewriting: Algorithmic Complexity of Term Rewriting Systems (CC, SK, MS), pp. 256–273.
ASPLOS-1987-DavidsonV #memory management #performance #set: The Effect of Instruction Set Complexity on Program Size and Memory Performance (JWD, RAV), pp. 60–64.
CAAP-1987-Szpankowski #approach #multi: Average Complexity of Additive Properties for Multiway Tries: A Unified Approach (Extended Abstract) (WS), pp. 13–25.
CAAP-1987-Wegener #branch #clique #on the #source code: On the Complexity of Branching Programs and Decision Trees for Clique Functions (IW), pp. 1–12.
STOC-1987-BilardiP #network: Size-Time Complexity of Boolean Networks for Prefix Computations (GB, FPP), pp. 436–442.
STOC-1987-ChazelleEG: The Complexity of Cutting Convex Polytopes (BC, HE, LJG), pp. 66–76.
STOC-1987-Fortnow: The Complexity of Perfect Zero-Knowledge (LF), pp. 204–209.
STOC-1987-Furer #communication #power of: The Power of Randomness for Communication Complexity (MF), pp. 178–181.
STOC-1987-Kaltofen: Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials (EK), pp. 443–452.
STOC-1987-MillerT #parallel: Dynamic Parallel Complexity of Computational Circuits (GLM, SHT), pp. 254–263.
STOC-1987-Smolensky #algebra #bound #formal method: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity (RS), pp. 77–82.
CSL-1987-KarpinskiBS #horn clause #on the #quantifier: On the Computational Complexity of Quantified Horn Clauses (MK, HKB, PHS), pp. 129–137.
CSL-1987-LenzW #polynomial: The Conjunctive Complexity of Quadratic Boolean Functions (KL, IW), pp. 138–150.
CSL-1987-Schoning: Complexity Cores and Hard-To-Prove Formulas (US), pp. 273–280.
CSL-1987-Speckenmeyer #backtracking #on the #problem #satisfiability: On the Average Case Complexity of Backtracking for the Exact-Satisfiability Problem (ES), pp. 281–288.
ICALP-1986-HartmanisH: Complexity Classes Without Machines: On Complete Languages for UP (JH, LAH), pp. 123–135.
ICALP-1986-HartmanisLY #set: Containment, Separation, Complete Sets, and Immunity of Complexity Classes (JH, ML, YY), pp. 136–145.
ICALP-1986-Muller: Subpolynomial Complexity Classes of Real Functions and Real Numbers (NTM), pp. 284–293.
ICALP-1986-MullerSS #automaton #monad: Alternating Automata. The Weak Monadic Theory of the Tree, and its Complexity (DEM, AS, PES), pp. 275–283.
ICALP-1986-RosierY #concurrent #finite #on the #probability #source code #termination: On The Complexity of Deciding Fair Termination of Probabilistic Concurrent Finite-State Programs (LER, HCY), pp. 334–343.
GG-1986-AalbersbergER #strict: Restricting the complexity of regular DNLC languages (IJA, JE, GR), pp. 147–166.
GG-1986-CarlyleGP #generative #parallel: Complexity of pattern generation via planar parallel binary fission/fusion grammars (JWC, SAG, AP), pp. 515–533.
CSCW-1986-CashmanS #theory and practice: Achieving sustainable complexity through information technology: theory and practice (PMC, DS), pp. 307–317.
STOC-1986-HalpernV #reasoning: The Complexity of Reasoning about Knowledge and Time: Extended Abstract (JYH, MYV), pp. 304–315.
STOC-1986-Krentel #optimisation #problem: The Complexity of Optimization Problems (MWK), pp. 69–76.
ICLP-1986-MannilaU86 #on the #sequence #unification: On the Complexity of Unification Sequences (HM, EU), pp. 122–133.
PODS-1985-PapadimitriouY #concurrent #reliability: The Complexity of Reliable Concurrency Control (CHP, MY), pp. 230–234.
PODS-1985-Ramarao #commit #on the #protocol: On the Complexity of Commit Protocols (KVSR), pp. 235–244.
VLDB-1985-SheardS #automation #database #reasoning: Coping with Complexity in Automated Reasoning about Database Systems (TS, DWS), pp. 426–435.
ICALP-1985-BilardiP #sorting: The Influence of Key Length on the Area-Time Complexity of Sorting (GB, FPP), pp. 53–62.
ICALP-1985-OrponenRS #polynomial: Polynomial Levelability and Maximal Complexity Cores (PO, DAR, US), pp. 435–444.
RTA-1985-BenanavKN #problem: Complexity of Matching Problems (DB, DK, PN), pp. 417–429.
CAAP-1985-Chazelle #algebra #geometry #performance: Fast Searching in a Real Algebraic Manifold with Applications to Geometric Complexity (BC), pp. 145–156.
STOC-1985-CarterSW #backtracking: The Complexity of Backtrack Searches (LC, LJS, MNW), pp. 449–457.
STOC-1985-FichT #finite #parallel: The Parallel Complexity of Exponentiating Polynomials over Finite Fields (FEF, MT), pp. 38–47.
STOC-1985-GoldwasserMR #interactive: The Knowledge Complexity of Interactive Proof-Systems (SG, SM, CR), pp. 291–304.
STOC-1985-Huynh #commutative #equivalence #problem #symmetry: The Complexity of the Equivalence Problem for Commutative Semigroups and Symmetric Vector Addition Systems (DTH), pp. 405–412.
STOC-1985-Vazirani #communication #generative #sequence #towards: Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (UVV), pp. 366–378.
PODS-1984-GrahamV #axiom #consistency #database #on the: On the Complexity and Axiomatizability of Consistent Database States (MHG, MYV), pp. 281–289.
ICALP-1984-AfratiPP #graph: The Complexity of Cubical Graphs (FNA, CHP, GP), pp. 51–57.
ICALP-1984-ChazelleOSW #decidability: The Complexity and Decidability of Separation (BC, TO, ESS, DW), pp. 119–127.
ICALP-1984-Hromkovic #communication: Communication Complexity (JH), pp. 235–246.
ICALP-1984-Jerrum #generative #sequence: The Complexity of Finding Minimum-Length Generator Sequences (MJ), pp. 270–280.
ICALP-1984-Jung #matrix #on the #performance #probability #problem: On Probabilistic Tape Complexity and Fast Circuits for Matrix Inversion Problems (HJ), pp. 281–291.
ICALP-1984-Vitter #interface: Computational Complexity of an Optical Disk Interface (JSV), pp. 490–502.
ICSE-1984-Elshoff #metric: Characteristic Program Complexity Measures (JLE), pp. 288–293.
ICSE-1984-Tai #data flow #graph #metric: A Program Complexity Metric Based on Data Flow Information in Control Graphs (KCT), pp. 239–249.
STOC-1984-Ben-OrKR #algebra #geometry: The Complexity of Elementary Algebra and Geometry (MBO, DK, JHR), pp. 457–464.
STOC-1984-DurisGS #bound #communication: Lower Bounds on Communication Complexity (PD, ZG, GS), pp. 81–91.
STOC-1984-Leighton #bound #parallel #sorting: Tight Bounds on the Complexity of Parallel Sorting (FTL), pp. 71–80.
CADE-1984-PelinG #algebra #problem #using #word: Solving Word Problems in Free Algebras Using Complexity Functions (AP, JHG), pp. 476–495.
PODS-1983-Cosmadakis #query #relational: The Complexity of Evaluating Relational Queries (SSC), pp. 149–155.
ICALP-1983-Gabarro: Initial Index: A New Complexity Function for Languages (JG), pp. 226–236.
ICALP-1983-Indermark #infinity: Complexity of Infinite Trees (KI), pp. 347–360.
ICALP-1983-Orponen: Complexity Classes of Alternating Machines with Oracles (PO), pp. 573–584.
ICALP-1983-RestM #finite #on the: On the Group Complexity of a Finite Language (EBLR, SWM), pp. 433–444.
STOC-1983-Engelfriet #automaton: Iterated Pushdown Automata and Complexity Classes (JE), pp. 365–373.
STOC-1983-Immerman: Languages Which Capture Complexity Classes (NI), pp. 347–354.
STOC-1983-Sipser #set: Borel Sets and Circuit Complexity (MS), pp. 61–69.
STOC-1983-Sipser83a #approach: A Complexity Theoretic Approach to Randomness (MS), pp. 330–335.
STOC-1983-Stockmeyer #approximate: The Complexity of Approximate Counting (LJS), pp. 118–126.
ICALP-1982-SelmanY #problem: The Complexity of Promise Problems (ALS, YY), pp. 502–509.
ICSE-1982-PotierAFB #reliability: Experiments with Computer Software Complexity and Reliability (DP, JLA, RF, AB), pp. 94–103.
DAC-1982-Adshead #algorithm #hardware #problem #question #scalability #towards: Towards VLSI complexity: The DA algorithm scaling problem: can special DA hardware help? (HGA), pp. 339–344.
STOC-1982-Greenberg #communication #on the: On the Time Complexity of Broadcast Communication Schemes (AGG), pp. 354–364.
STOC-1982-PapadimitriouS #communication: Communication Complexity (CHP, MS), pp. 196–200.
STOC-1982-PapadimitriouY: The Complexity of Facets (and Some Facets of Complexity) (CHP, MY), pp. 255–260.
STOC-1982-SistlaC #linear #logic: The Complexity of Propositional Linear Temporal Logics (APS, EMC), pp. 159–168.
STOC-1982-Vardi #query #relational: The Complexity of Relational Query Languages (MYV), pp. 137–146.
ILPC-1982-Shapiro82 #logic programming #source code: Alternation and the Computational Complexity of Logic Programs (EYS), pp. 154–163.
ICALP-1981-GurariI #multi #problem: The Complexity of Decision Problems for Finite-Turn Multicounter Machines (EMG, OHI), pp. 495–505.
ICALP-1981-IbarraLM #on the: On the Complexity of Simple Arithmetic Expressions (OHI, BSL, SM), pp. 294–304.
ICALP-1981-Lieberherr: Uniform Complexity and Digital Signatures (KJL), pp. 530–543.
ICSE-1981-SunoharaTUO #development: Program Complexity Measure for Software Development Management (TS, AT, KU, TO), pp. 100–106.
STOC-1981-AdachiIK #combinator #game studies #low level: Low Level Complexity for Combinatorial Games (AA, SI, TK), pp. 228–237.
STOC-1981-Chan: Reversal Complexity of Counter Machines (ThC), pp. 146–157.
STOC-1981-ChazelleM: A Model of Computation for VLSI with Related Complexity Results (BC, LM), pp. 318–325.
STOC-1981-HongK #game studies: I/O Complexity: The Red-Blue Pebble Game (JWH, HTK), pp. 326–333.
STOC-1981-Leivant #independence #parametricity #polymorphism #programming language #theorem: The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories) (DL), pp. 38–45.
STOC-1981-Orlin #optimisation #problem: The Complexity of Dynamic Languages and Dynamic Optimization Problems (JBO), pp. 218–227.
STOC-1981-Simon #bound #probability #turing machine: Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (JS), pp. 158–167.
ICALP-1980-EvenY: Cryptocomplexity and NP-Completeness (SE, YY), pp. 195–207.
ICALP-1980-Furer #problem #regular expression: The Complexity of the Inequivalence Problem for Regular Expressions with Intersection (MF), pp. 234–245.
ICALP-1980-Huynh #linear #set: The Complexity of Semilinear Sets (TDH), pp. 324–337.
ICALP-1980-Snir #on the: On the Size Complexity of Monotone Formulas (MS), pp. 621–631.
POPL-1980-Parikh #logic #modelling #source code: Propositional Logics of Programs: Systems, Models, and Complexity (RP), pp. 186–192.
DAC-1980-Donath #automation #design: Complexity theory and design automation (WED), pp. 412–419.
DAC-1980-SahniB #automation #design #problem: The complexity of design automation problems (SS, AB), pp. 402–411.
STOC-1980-BrentK: The Chip Complexity of Binary Arithmetic (RPB, HTK), pp. 190–200.
STOC-1980-EhrigM #algebra #implementation #specification: Complexity of Implementations on the Level of Algebraic Specifications (HE, BM), pp. 281–293.
STOC-1980-Hong #on the #problem: On Some Deterministic Space Complexity Problems (JWH), pp. 310–317.
STOC-1980-IbarraL #equivalence #problem #source code: The Complexity of the Equivalence Problem for Straight-Line Programs (OHI, BSL), pp. 273–280.
STOC-1980-KarpL: Some Connections between Nonuniform and Uniform Complexity Classes (RMK, RJL), pp. 302–309.
SIGMOD-1979-HuntR #testing: The Complexity of Testing Predicate Locks (HBHI, DJR), pp. 127–133.
ICALP-1979-BookB #representation #set #similarity: Representing Complexity Classes by Equality Sets (RVB, FJB), pp. 49–57.
ICALP-1979-PapadimitriouY #problem #strict: The Complexity of Restricted Minimum Spanning Tree Problems (CHP, MY), pp. 460–470.
ICALP-1979-Ruzzo #context-free grammar #on the #parsing #recognition: On the Complexity of General Context-Free Language Parsing and Recognition (WLR), pp. 489–497.
ICSE-1979-CurtisSM #metric #performance #predict #replication: Third Time Charm: Stronger Replication of the Ability of Software Complexity Metrics to Predict Programmer Performance (BC, SBS, PM), pp. 356–360.
STOC-1979-DeMilloL #logic: Some Connections between Mathematical Logic and Complexity Theory (RAD, RJL), pp. 153–159.
STOC-1979-GurariI #equivalence #linear #problem #set #source code: The Complexity of the Equivalence Problem for Counter Machines, Semilinear Sets, and Simple Programs (EMG, OHI), pp. 142–152.
STOC-1979-JaJa #commutative #on the: On the Complexity of Bilinear Forms with Commutativity (JJ), pp. 197–208.
STOC-1979-Ladner #communication #csp #problem #process: The Complexity of Problems in Systems of Communicating Sequential Processes (REL), pp. 214–223.
STOC-1979-SedgewickS: The Complexity of Finding Periods (RS, TGS), pp. 74–80.
STOC-1979-Shamir #on the: On the Cryptocomplexity of Knapsack Systems (AS), pp. 118–129.
STOC-1979-Thompson: Area-Time Complexity for VLSI (CDT), pp. 81–88.
STOC-1979-Yao: Some Complexity Questions Related to Distributive Computing (ACCY), pp. 209–213.
ICALP-1978-Berman: Relationship Between Density and Deterministic Complexity of NP-Complete Languages (PB), pp. 63–71.
ICALP-1978-FortuneHS #equivalence #for free: The Complexity of Equivalence and Containment for Free Single Variable Program Schemes (SF, JEH, EMS), pp. 227–240.
ICALP-1978-Savitch #nondeterminism #parallel: Parallel and Nondeterministic Time Complexity Classes (WJS), pp. 411–424.
GG-1978-PazR #generative: Complexity of Pattern Generation by Map-L-Systems (AP, YR), pp. 367–378.
POPL-1978-OgdenRR #concurrent: Complexity of Expressions Allowing Concurrency (WFO, WER, WCR), pp. 185–194.
ICSE-1978-McClure #analysis: A Model for Program Complexity Analysis (CLM), pp. 149–157.
STOC-1978-Lewis #on the #problem: On the Complexity of the Maximum Subgraph Problem (JML), pp. 265–274.
STOC-1978-Lynch #metric #parametricity: Straight-Line Program Length as a Parameter for Complexity Measures (NAL), pp. 150–161.
STOC-1978-Pan: Computational Complexity of Computing Polynomials over the Fields of Real and Complex Numbers (VYP), pp. 162–172.
STOC-1978-Schaefer #problem #satisfiability: The Complexity of Satisfiability Problems (TJS), pp. 216–226.
STOC-1978-Wegener #polynomial: Switching Functions Whose Monotone Complexity Is Nearly Quadratic (IW), pp. 143–149.
ICALP-1977-Alton #memory management #metric: “Natural” Complexity Measures and Time versus Memory: Some Definitional Proposals (DAA), pp. 16–29.
ICALP-1977-Erni #on the: On the Time and Tape Complexity of Hyper(1)-AFL’s (WJE), pp. 230–243.
ICALP-1977-JonesS #problem: Complexity of Some Problems Concerning L Systems (NDJ, SS), pp. 301–308.
ICALP-1977-Sudborough: The Time and Tape Complexity of Developmental Languages (IHS), pp. 509–523.
STOC-1977-Brown #maintenance #queue: The Complexity of Priority Queue Maintenance (MRB), pp. 42–48.
STOC-1977-Hartmanis #proving: Relations Between Diagonalization, Proof Systems, and Complexity Gaps (JH), pp. 223–227.
STOC-1977-Kozen #algebra: Complexity of Finitely Presented Algebras (DK), pp. 164–177.
ICALP-1976-AltM #bound #recognition: Lower Bounds for the Space Complexity of Context-Free Recognition (HA, KM), pp. 338–354.
POPL-1976-Hunt #problem: A Complexity Theory of Grammar Problems (HBHI), pp. 12–18.
ICSE-1976-McCabe: A Complexity Measure (TJM), p. 407.
STOC-1976-PapadimitriouS #problem: Some Complexity Results for the Traveling Salesman Problem (CHP, KS), pp. 1–9.
STOC-1976-Schaefer #finite #game studies #problem: Complexity of Decision Problems Based on Finite Two-Person Perfect-Information Games (TJS), pp. 41–49.
POPL-1975-HuntSU #lr #on the #testing: On the Complexity of LR(k) Testing (HBHI, TGS, JDU), pp. 130–136.
POPL-1975-JazayeriOR #attribute grammar #on the: On the Complexity of the Circularity Test for Attribute Grammars (MJ, WFO, WCR), pp. 119–129.
STOC-1975-Galil #bound #on the: On the Validity and Complexity of Bounded Resolution (ZG), pp. 72–82.
STOC-1975-GinsburgL #comparative: Comparative Complexity of Grammar Forms (SG, NAL), pp. 153–158.
STOC-1975-HuntS #on the #problem: On the Complexity of Grammar and Related Problems (HBHI, TGS), pp. 54–65.
STOC-1975-HyafilK #evaluation #linear #parallel: The Complexity of Parallel Evaluation of Linear Recurrence (LH, HTK), pp. 12–22.
STOC-1975-LiptonD #evaluation #integer #metric: Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms (RJL, DPD), pp. 1–5.
STOC-1975-LiptonED #data type: The Complexity of Control Structures and Data Structures (RJL, SCE, RAD), pp. 186–193.
STOC-1975-Paul #bound #combinator: A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions (WJP), pp. 27–36.
STOC-1975-Shamos #geometry: Geometric Complexity (MIS), pp. 224–233.
STOC-1975-Valiant #bound #on the: On Non-linear Lower Bounds in Computational Complexity (LGV), pp. 45–53.
STOC-1975-Wagner #on the #problem #string: On the Complexity of the Extended String-to-String Correction Problem (RAW), pp. 218–223.
ICALP-1974-Ausiello #recursion #semantics #source code: Relations between Semantics and Complexity of Recursive Programs (GA), pp. 129–140.
ICALP-1974-Book #on the: On the Structure of Complexity Classes (RVB), pp. 437–445.
ICALP-1974-Weihrauch: The Compuational Complexity of Program Schemata (KW), pp. 326–334.
STOC-1974-EhrenfeuchtZ #metric #regular expression: Complexity Measures for Regular Expressions (AE, HPZ), pp. 75–79.
STOC-1974-Gill #probability #turing machine: Computational Complexity of Probabilistic Turing Machines (JTGI), pp. 91–95.
STOC-1974-Miller: Computational Complexity and Numerical Stability (WM), pp. 317–322.
STOC-1974-Rackoff #on the: On the Complexity of the Theories of Weak Direct Products: A Preliminary Report (CR), pp. 149–160.
STOC-1974-Robertson #higher-order #monad: Structure of Complexity in the Weak Monadic Second-Order Theories of the Natural Numbers (ELR), pp. 161–171.
SIGIR-1973-Winograd: Breaking the Complexity Barrier again (TW), pp. 13–30.
STOC-1973-Constable: Type Two Computational Complexity (RLC), pp. 108–121.
STOC-1973-HopcroftM #matrix #multi: Duality Applied to the Complexity of Matrix Multiplications and other Bilinear Forms (JEH, JM), pp. 73–87.
STOC-1973-Hunt #on the: On the Time and Tape Complexity of Languages I (HBHI), pp. 10–19.
STOC-1973-Kung #algebra: The Computational Complexity of Algebraic Numbers (HTK), pp. 152–159.
ICALP-1972-Bertoni #approximate #probability #problem: Complexity Problems Related to the Approximation of Probabilistic Languages and Events by Deterministic Machines (AB), pp. 507–516.
ICALP-1972-Boas #comparison: A Comparison of the Properties of Complexity Classes and Honesty Classes (PvEB), pp. 391–396.
ICALP-1972-Book #formal method: Complexity Classes of Formal Languages (RVB), pp. 517–520.
ICALP-1972-Turner #approach #infinity: An Infinite Hierarchy of Term Languages — An Approach to Mathematical Complexity (RT), pp. 593–608.
STOC-1972-Cook #nondeterminism: A Hierarchy for Nondeterministic Time Complexity (SAC), pp. 187–192.
STOC-1972-Schnorr #effectiveness #process #random testing #testing: The Process Complexity and Effective Random Tests (CPS), pp. 168–176.
STOC-1971-ConstableH: Complexity of Formal Translations and Speed-Up Results (RLC, JH), pp. 244–250.
STOC-1971-Cook: The Complexity of Theorem-Proving Procedures (SAC), pp. 151–158.
STOC-1971-Robertson #recursion: Complexity Classes of Partial Recursive Functions (ELR), pp. 258–266.
STOC-1970-BassY #set: Hierarchies Based on Computational Complexity and Irregularities of Class Determining Measured Sets (LJB, PRY), pp. 37–40.
STOC-1970-Burkhard #problem #realtime: Complexity Problems in Real Time Computation (WAB), pp. 62–69.
STOC-1970-LandweberR #recursion: Recursive Properties of Abstract Complexity Classes (LHL, ELR), pp. 31–36.
STOC-1970-Lewis: Unsolvability Considerations in Computational Complexity (FDL), pp. 22–30.
STOC-1969-Avizienis #on the #problem: On the Problem of Computational Time and Complexity of Arithmetic Functions (AA), pp. 255–258.
STOC-1969-Borodin #recursion: Complexity Classes of Recursive Functions and the Existence of Complexity Gaps (AB), pp. 67–78.
STOC-1969-Hodes #geometry #logic: The Logical Complexity of Geometric Properties in the Plane (LH), pp. 249–254.
STOC-1969-Loveland #metric #on the: On Minimal-Program Complexity Measures (DWL), pp. 61–65.