BibSLEIGH
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
complexity
Google complexity

Tag #complexity

1390 papers:

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

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