A Complete Bibliography of ACM Transactions on Computation Theory (ToCT)

Nelson H. F. Beebe University of Utah

Department of Mathematics, 110 LCB

155 S 1400 E RM 233 Salt Lake City, UT 84112-0090

USA

Tel: +1 801 581 5254 FAX: +1 801 581 4148

E-mail: beebe@math.utah.edu, beebe@acm.org, beebe@computer.org (Internet)
WWW URL: https://www.math.utah.edu/~beebe/

23 December 2023 Version 1.38

Title word cross-reference

(·, H) [yCG21]. 0 [FPS15]. 1 [AOTW14, Cha18]. 2 [AOTW14, GL18, Hru16]. 3 [AOTW14, Zeh23]. ^{0} [CTW13]. ∩ [AT11]. d [AA20]. H [BCKP18, yCG21, CJO^{+}23, GGJ17]. k [AFS^{+}18, Bla19, LS21, Zeh23]. k ≥ 5 [Sch19]. O(nϵ) [CT18]. O(\sqrt{n}) [RRS^{+}12]. O ∗ (8.097^{k}) [Zeh23]. Ω((n log n)/R) [Ail16]. q [OWZ14]. R [Ail16, Chi21]. W [1] [PW18a].

-Coloring [AOTW14, CJO^{+}23]. -Colorings [GGJ17]. -free [BCKP18]. -Frege [FPS15]. -hard [PW18a]. -ic [Chi21]. -Median [Cha18]. -packing [Zeh23]. -Reducible [CTW13]. -set [Zeh23]. -Spin [GL18].

-time [Zeh23]. -to- [AOTW14]. -Uniform [AA20, Bla19, LS21]. -Well [Ail16].

2Lin [OWZ15].

3-Query [BSHLM09, GR09]. 3Lin [OWZ15].

above [CPPW13]. Abstract [BGMS16, BBDL^{+}21]. AC [CTW13, FPS15]. AC0 [Vio21]. Advantage [RV13]. adversarial [Dru13]. Adversary [AKP^{+}21]. Advice [Wat14]. Affine [AB18, AB19, BG17]. Affine-Invariant [BG17]. against [CMS20]. Algebraic [AFS^{+}18, CLV21, KNST19, KNS20]. Algebrization [AW09, AB18, AB19]. Algorithm [CT18, Zeh23]. Algorithmic [DK13, FGST22, LL18, Lut21]. Algorithms [CFM14, FMMS20, GGS21, GKM20, HH13, KKL^{+}21, LPRV22, PW18b, TKM12, FJ14]. Allowing [FLOR15]. Almost [AT11, Juk20]. ALOGTIME [BFLW22]. ALOGTIME-hard [BFLW22]. Alternation [Che17, Wil13]. Alternation-Trading [Wil13]. Amortization [AA20]. Analysis [KC12]. Anti [CKW19]. Anti-Gadgets [CKW19]. Application [ESY14]. Approximability [GJL^{+}21, ST19]. Approximate [BZ20, DL21, HV22, OS18, Smy11, TZ15]. Approximately [FGZ20, GGJ17, GJ14]. Approximating [BH12, BGGS21, CHIS12, GJ19, RRS^{+}12, RT13]. Approximation [AKPP17, BCKP18, Cha18, GL18, RT16]. Approximations [GJL^{+}16]. Arithmetic [KMS16, Kum20, Vol16]. Arrangement [FHRS16]. Arthur [PV12a, Wat20a]. Asking [CL17]. Auction [CKK16]. Average [HS10, Wat12]. Average-Case [HS10, Wat12]. Avoidability [IOO21].

Balancing [GL19]. Barrier [AW09]. Barriers [AB18, AB19]. Based [BCJ19, GR16, RR22]. Bazzi [Raz09]. Beating [Ros20]. Being [ACC^{+}14]. Better [Sch19]. Betting [HH13]. Between [KNS20, DPV09, HO20, Sch17, Sri20]. Beyond [PS20, ST19, Sch16]. Bidders [CKK16]. Binary [JP19]. Bipartite [GGS21]. Bits [GV20]. Boolean [AS17, BWZ21, FUZ19, HR16, DP19, RRS^{+}12]. Bootstrapping [BGV14]. Border [Kum20]. Bound [Ail16, BGMS16, GW20, Lau16, Ros20, VK22]. Boundary [HO20]. Bounded [BGLR12, BHLV19, ES17, KV10]. Bounded-Depth [BGLR12]. Bounding [Kre21]. Bounds [AGSU15, AFS^{+}18, ACK^{+}21, BG17, BCG19, BłKP^{+}19, CJO^{+}23, CKLM20, DW12, DKS19, FPS15, FLM^{+}21, HH13, KKL^{+}21, KPW20, KS15, Kom18, KPRR14, KMS16, OWZ14, Pur11, Wat14, Wil13, CPPW13, RR19].

Branching

[AFS^{+}18, CMW^{+}12, CM23, DKS19, GV20, IN19, KNST19, KNS20, KS15].

Caching [BIPS10, ERSV13]. cactus [GGR14]. Calculi [BCJ19]. Can [BMT21, MYKM21, Zeh23]. Candidate [CEMT14]. Canonizing [ES17]. Case [HS10, KV10, Wat12, ST19]. Catalytic [CM23]. Categorical [BFGS23]. CDS [AA20]. Cell [Yin10]. Cell-Probe [Yin10]. Characteristic [CS23, Hru16]. Characterization [DKS19]. characterized [FJ14]. Characterizing [Vol16]. Chief [O’D20]. Chordal [GJL^{+}21]. Circuit [AH19, CKLM20, HH13, KMS16, CFL14]. Circuits [AS17, Chi21, GHKL18, KNS20, Kum20, VK22]. Classes [AJR16, CLV21, GJL^{+}21, HSS21]. Classical [AKP^{+}21]. Classification [CM15]. Clique [CKP^{+}14]. Clones [FZ16]. Clustering [BFGS23]. CNF [HO20, RW20]. Co [KPRR14]. Co-Nondeterminism [KPRR14]. Coarse [LW22]. Codes [GM12, GGK19, STV20, Vid13]. Coin [Juk20, LV18, Pur11]. Coin-Weighing [Pur11]. Collision [HM23]. Collusion [PV12b]. Collusion-Resistant [PV12b]. Coloring [AOTW14, CJO^{+}23]. Colorings [GGJ17]. Colouring [LMP19]. Colourings [GGW22, NŽ22]. Communication [AGSU15, BCG19, BKM18, DPV09, FJK^{+}16, GJPW18, KKL^{+}21, KPS19, Wat18]. Compact [GMPS14]. comparator [CFL14]. Comparing [ESY14]. Complete [AJR16, CLV21, GHPT14, GKMT17, MV18, BFLW22]. Completeness [Hru16]. Completion [DFPV15]. Complex [BGGS21]. Complexity [AW09, AGSU15, AFK^{+}22, BFGS23, BCJ19, BGGS21, BCG19, BM15, BłKP^{+}19, BWZ21, CKW19, Cha18, CLV21, Che17, DFPV15, ESY14, FM23, FGMN11, FMMS20, FGZ20, FJK^{+}16, FUZ19, GGJ17, GKM20, GJ14, GM15, GMPS14, HPV11, HSS21, IOO21, JLR21, KC12, KRU19, KPW20, KPS19, KMW16, LS21, MN22, RW20, RRS^{+}12, Sch16, SV12, Smy11, VLB12, Wat18, CFL14, GGR14]. Compressed [BFLW22, Pag13]. Computation [Ail16, BBDL^{+}21, FLM^{+}21]. Computational [IOO21, SV12, VLB12]. Computer [AG14, AG13]. Computing [Chi21]. Concisely [SV12]. Condensers [ATS19]. Conditional [BC18, LL18, RT16]. Conditioned [Ail16]. confidence [Dru13]. Conjecture [SS22]. Conjunctive [CM15]. Connecting [FJ14]. Connection [BCE^{+}19, FZ16]. Connectivity [GS18]. coNP [AT11]. Consensus [Sch17]. Constant [AA20, BG17, PV12a, Vio19, BDK^{+}13]. Constant-Error [Vio19]. Constant-Round [PV12a]. Constraint [CL17, JLR21]. Constraints [KPW20]. Constructing [CS23]. Contraction [ALSZ19, FLM^{+}21, GJL^{+}21]. Controller [VLB12]. Convergence [SZ14]. Cops [GTT20]. Correctness [GM12]. Correlated [CKK16]. Correlations [GJ19]. Corrigendum [AB19]. Counting [BZ20, DL21, FGZ20, GGJ17, GGW22, GGR16, GJ14, JM15, OS18, GGR14]. Cover [AOTW14, CKP^{+}14]. CSP [BZ20, LW20, LW22]. CSPs [DK13, FUZ19, JP19, TZ18]. CTC [OS18]. cut [CPPW13]. Cutting [Lau16]. Cyclic [OWZ15].

Data [BFGS23]. Decidability [TZ15]. Decision [DL21, HHM20]. Decodable [GM12]. Decoders [GGK19]. Decoding [HR16, STV20, Vid13]. Decompositions [PW18b]. Degree [BKT13, HV22, JP19, VK22]. Deletion [FGMN11, Kom18]. Dense [Wat14]. Depth [BGLR12, Chi21, KNS20, KLMS16, Kum20, BDK^{+}13]. Depth-3 [Kum20]. Depth-three [KNS20]. Derandomization [MV18].

Derivative [KMS16]. Design [CKK16]. Determinants [DKLM10]. Determines [yCG21]. Deterministic [AGSU15, CKK16]. Dichotomy [CKW19, FGMN11]. Difference [Sch17]. Differential [SZ14]. Digraphs [LMP19]. Dimension [CL15, DKS19, LL18, Lut21]. Direct [GS20]. Directed [BTV09, CT18, FM23, KV10, PW18a]. Discrepancy [FJK^{+}16]. Disjoint [FGMN11, GHPT14, GW20]. Disjointness [MN22, PS20]. Distance [AGSU15, Wat18]. Distortion [FFL^{+}13]. Distributed [MN22]. Distribution [BCG19, RR22]. Distribution-Free [RR22]. Distributions [BC18]. Do [GKM^{+}16]. Does [FJK^{+}16]. Domains [BWZ21]. DPLL [BIPS10]. Dynamic [Juk20].

Economical [ERSV13]. Edge [BCKP18]. Editor [For09, O’D20]. Editor-in-Chief [O’D20]. Editorial [O’D20]. Effective [SZ14]. Efficiency [PW18b]. Efficient [FMMS20, GJL^{+}16]. Election [HHM20, TKM12]. Elementary [Sch16]. Embedding [GKM20]. Encryption [BGV14]. Entropy [ACK^{+}21, ATS19, KS15]. Enumeration [Ros20]. Equations [SZ14, VK22]. Equilibria [HS10, SV12]. Equivalent [AKP^{+}21]. Erasure [LPRV22]. Erasure-Resilient [LPRV22]. Error [RR22, Vio19]. ETH [GdHKS20]. Evaluation [CMW^{+}12, IN19]. Evasive [Bla19]. Even [PW18a]. Evolvability [Val14]. Exact [GKMT17, HH13, HO20, KMW16, TKM12]. Example [RT16]. Except [OWZ14]. Exist [GKM^{+}16]. Existential [GdHKS20]. expander [Vid13]. Expanders [GGS21]. Experts [KS14]. Explicit [DM13]. Exploring [DFPV15]. Exponential [FPS15, GM12, Sri20]. Expressions [GHKL18]. Extensions [LW20].

Extraction [HPV11]. Extractors [DW12].

Faithful [CS23]. Families [JM15, KPS19]. Family [BBDL^{+}21]. Fast [GGS21]. Faster [Zeh23]. Feasible [Fol23]. Feature [BFGS23]. Feedback [ALMS18]. Ferromagnetic [GL18]. Few [KPW20]. Fields [BKT13, CS23]. Filters [AJMR14]. Finding [FGMN11, HM23, KPRR14, Sch17]. Fine [CM15, DL21, JLR21, LW22]. Fine-Grained [DL21, JLR21, LW22]. Finite [CS23, GHKL18, STV20]. Fixed [FM23, FFL^{+}13]. Fixed-Parameter [FM23]. Fixing [AFK^{+}22]. Flipping [Juk20]. FOL [FGST22]. Forbidden [Hav19]. Foreword [For09]. Forgetfulness [Zeh23]. Formula [BIPS10, FGL16]. Formulae [Vol16]. Formulas [GTT20, KKL^{+}21, MV18, RR19]. Formulation [BGMS16]. Four [Chi21, PW18a]. Fourier [Ail16, ACK^{+}21, HR16]. Fourier-Sparse [HR16]. FPT [FJ14, GKM20]. Fractal [Lut21]. Free [GGR16, RR22, BCKP18]. Freeness [RR22]. Frege [BGLR12, FPS15]. Frequency [BH12]. Full [KNST19]. Fully [BGV14]. Function [BCE^{+}19, CEMT14, RT13]. Functions [AKP^{+}21, AJMR14, BKT13, HR16, DP19, PRV18, RRS^{+}12, Val14].

Gadgets [CKW19, GKM^{+}16]. Galois [FZ16]. Games [GTT20, GMPS14, HH13, RW20, RV15, SV12, Wat20a]. Gap [ATS19]. Gates [KKL^{+}21]. Gaussian [DM13]. General [CM23, FUZ19, GGS21, GS20, TZ18]. General-Valued [FUZ19, TZ18]. Generator [Ros20]. Generator-Enumeration [Ros20]. Generators [AS17, CKLM20]. Genus [KV10]. Geometrical [BBDL^{+}21]. Geometry [SS22]. Goldreich [CEMT14]. Grained [DL21, JLR21, LW22]. Graph [CTW13, CKP^{+}14, DLN^{+}22, FGST22, KPS19, LPRV22]. Graphic [GKM20]. Graphs [AFK^{+}22, CT18, ES17, GGR16, GJL^{+}21, GKMT17, Kul11, KV10, PW18b, GGR14]. Grids [STV20]. Ground [GS18]. Group [AT11, CTW13, RT16, Ros20]. Groups [BFLW22, CM23, OWZ15].

H [LMP19]. H-Colouring [LMP19]. Hadwiger [FLM^{+}21]. Hamiltonians [GS18]. Hamming [AGSU15]. Hamming-Distance [AGSU15]. Hard [BKT13, CFM14, JM15, Vio16, BFLW22, GMSZ21, PW18a, LW22]. Hardness [ACC^{+}14, AKPP17, AOTW14, BHP20, BCKP18, Che17, DK13, DM13, GR09, Hru16, OWZ15, Vio19, AH19]. Hashing [OWZ14]. Hereditary [KPRR14]. Hidden [RT16]. Hierarchies [Sch16]. Hierarchy [Che17]. High [Dru13]. High-confidence [Dru13]. Higher [GM12]. Homomorphic [BGV14]. Homomorphism [CLV21]. Homomorphisms [CS23, GGR16, GJ14, GGR14]. Horn [HO20]. Hurdles [KS14]. Hypergraph [GGW22, LS21]. Hypergraphs [Bla19, NŽ22]. hyperplane [SS22].

ic [Chi21]. Identity [AFS^{+}18, MV18]. II [AG14]. Imply [FPS15]. Improved [ACK^{+}21, DPV09]. Inapproximability [GGW22]. Incidence [SS22]. Incompressibility [CKP^{+}14]. Increase [BMT21]. Independence [BHLV19]. Indistinguishability [HV22]. Individualization [AFK^{+}22]. Induced [KPRR14]. Infinite [FZ16]. Influence [RRS^{+}12, ST19]. Information [AA20, FJK^{+}16, KRU19, LL18]. Inner [PS20]. Innovations [AG14, AG13]. Input [GM15, Sch17]. Input-Oblivious [GM15]. Insights [AH19]. Instances [CFM14]. Integer [KPW20]. Integers [ESY14, GR09, OWZ15]. Interpolation [Fol23]. Intersection [BMT21]. Intersections [Lut21]. Intrinsically [BBDL^{+}21]. Introduction [AG13, AG14]. Invariance [FKMW18]. Invariant [BG17]. Ising [GJ19]. Isolation [Kul11]. Isomorphism [AT11, BCE^{+}19, yCG21, CTW13, DLN^{+}22, Ros20]. Issue [AG14, AG13].

Joint [BC18]. Junta [BCE^{+}19].

Kakeya [LL18]. Kernel [KPRR14]. Kernelizability [KMW16]. Kernels [FLOR15, FJ14]. Kolmogorov [HPV11].

Label [AOTW14]. Landscape [FM23]. Large [OWZ15]. Layered [CT18]. LCCs [BG17]. Leader [TKM12]. Leading [CKW19]. Leaf [KKL^{+}21]. Learning [HH13, HO20, KS14]. Length [AS17, GM12, Sch17]. Leveled [BGV14]. Lifting [Wat20b]. Limitations [AJMR14, CKK16]. Limits [TZ18]. Line [MN22]. Linear [CHIS12, FHRS16, GR09, KPW20, DP19, Vid13, VK22, Wil13]. Linear-time [Vid13]. Linearity [CMS20]. Linearly [NŽ22]. Lipschitz [AJMR14]. List [CJO^{+}23, GGJ17, HR16]. List-Decoding [HR16]. Local [AJMR14, CKLM20, GS18, GGK19]. Locality [OWZ14]. Locality-Sensitive [OWZ14]. Localize [MYKM21]. Locally [DW12, GM12, GGK19]. Log [BTV09, DLN^{+}22, SS22]. Log-rank [SS22]. Log-Space [BTV09, DLN^{+}22]. Logarithmic [CM15]. Logarithmically [PS20]. Logspace [ES17, KV10]. Long [BSHLM09]. Loss [ATS19]. Lovász [yCG21]. Low [BKT13, GKM20, JP19, KKL^{+}21]. Low-Communication [KKL^{+}21]. Low-Complexity [GKM20]. Low-Degree [BKT13, JP19]. Lower [Ail16, AGSU15, AFS^{+}18, BGMS16, BG17, BCG19, BłKP^{+}19, CJO^{+}23, CKLM20, DW12, DKS19, FPS15, FLM^{+}21, GW20, HH13, KKL^{+}21, KPW20, KS15, Kom18, KPRR14, Kre21, KMS16, Lau16, OWZ14, Pur11, RR19, Wat14, Wil13, CPPW13]. LTCs [BG17].

Machines [BBDL^{+}21]. Majority [Vio19]. Make [Zeh23]. Manipulation [HHM20]. Many [PS20]. Maps [Vio16]. Matching [BGGS21, FMMS20, GMSZ21, GKM^{+}16, GKMT17]. Matchings [DKLM10]. Matrices [KMS16, VK22]. matrix [Pag13]. Max [KMW16, OWZ15]. Max-2Lin [OWZ15]. Max-3Lin [OWZ15]. Max-Poly [DSS17]. Maximization [ST19]. Maximum [ESY14, KMS16]. Maximum-Rank [KMS16]. MCSP [CKLM20]. Mechanisms [PV12b]. Median [Cha18]. Merlin [PV12a, Wat20a]. Meta [FGST22]. Meta-Theorem [FGST22]. Metaquestions [CL17]. Method [BGMS16]. Methods [AKP^{+}21]. Metric [Cha18]. Metrics [GKM20]. Midpoint [MYKM21]. Min [ACK^{+}21, DSS17]. Min-entropy [ACK^{+}21]. Min/Max [DSS17]. Min/Max-Poly [DSS17]. Minimal [TZ15]. Minimization [AH19]. Minimum [FHRS16]. Minrank [Hav19]. Mixing [GL18]. Model [Ail16, GJ19, GR20, Wat14]. Modification [BCKP18, FGST22]. Modulo [Che17, GGR16, GGR14]. Moments [BH12]. Monotone [AJMR14, Bla19, Fol23, DP19, RRS^{+}12, Sri20]. Morgan [KKL^{+}21]. MSO [GdHKS20]. Muller [STV20]. Multi [Chi21, KRU19]. Multi- [Chi21]. Multi-Party [KRU19]. Multicoloring [BłKP^{+}19]. Multicut [PW18a]. Multilinear [Chi21, KNS20]. Multilinearization [Hru16]. Multiparty [DPV09]. Multiple [BH12, HM23]. multiplication [Pag13]. multiway [CPPW13]. Mutual [CL15].

Nash [SV12]. Neciporuk [BGMS16]. Network [FM23]. NL [DSS17]. Non [AH19, AS17, BWZ21, CMS20, VK22]. Non- [AH19]. Non-Boolean [AS17, BWZ21]. Non-rigid [VK22]. Non-signaling [CMS20]. Nonautoreducible [NS16]. Noncommutative [AJR16]. Nondeterminism [BGMS16, KPRR14]. Nondeterministic [DPV09]. Nonsubmodular [ST19]. Note [ESY14]. NP [Wat20b, AT11, AOTW14, GHPT14, GMSZ21, LW22, Wat12]. NP-Complete [GHPT14]. NP-Hard [LW22, GMSZ21]. NP-Hardness [AOTW14]. Nucleolus [GMPS14]. Number [AFK^{+}22, FLM^{+}21, GJPW18, RT13]. Numerical [SZ14].

Oblivious [AFS^{+}18, GM15, GV20, KNS20]. obstruction [FJ14]. Once [FGL16, IN19, MV18, Vol16, KNS20, RR19]. One [CEMT14, RR22]. One-Sided [RR22]. One-Way [CEMT14]. Ones [KMW16]. Operators [KC12]. Optimal [AS17, BGLR12, DM13, JP19, OWZ14, PV12b, RR22]. Optimization [BCE^{+}19, VLB12]. Oracles [HSS21]. Ordered [NŽ22]. orders [FJ14]. Other [BZ20]. Overdetermined [GR09]. Overlaps [FLOR15].

P [GM15]. P/poly [GM15]. Packing [AKPP17, FLOR15, Zeh23]. Pairs [HM23, PW18a]. Pairwise [GJ19]. Parallel [PV12a]. Parameter [FM23, FFL^{+}13]. Parameterizations [FHRS16]. Parameterized [ALMS18, AFK^{+}22, BFGS23, BGLR12, CM15, GJL^{+}21, IY18, JM15, KMW16, PRV18, CPPW13]. Parametric [FLOR15]. Parsing [ESY14]. Part [AG14]. Partial [IOO21, KMS16]. Parties [PS20]. Partition [GJPW18].

Party [KRU19]. Pattern [FMMS20]. PCP [GR09]. PCPPs [BSHLM09]. Pebbles [CMW^{+}12]. Pebbling [KS15]. Perfect [GKM^{+}16, GKMT17]. Permanents [DKLM10]. Perspective [ALMS18, GM15]. Planar [BTV09, CT18, DLN^{+}22, Kul11, KV10]. Planarity [DKLM10, FGST22]. Planarizing [GKM^{+}16]. Plane [BGGS21, LL18]. Planes [Lau16]. Point [SS22]. Point-hyperplane [SS22]. Poly [AS17, DSS17, GM15]. Poly-Size [AS17]. Polynomial [BGGS21, CT18, Che17, FLOR15, HSS21, VK22]. Polynomial-Time [HSS21]. Polynomials [BKT13, CLV21, Chi21, JP19, KS12]. POMDPs [VLB12]. Popular [GMSZ21]. Power [AA20, Kul11, Kum20, OS18, RT16]. PPSZ [Sch19]. Predicates [CHIS12, AH13]. predictions [Dru13]. Prime [BKT13]. Principle [FKMW18]. Privacy [KRU19]. Private [ACC^{+}14]. Probability [ESY14]. Probe [Yin10]. Problem [DSS17, FHRS16, LV18, TKM12, CFL14]. Problems [AH19, AGSU15, AJR16, BFLW22, BCKP18, DFPV15, FM23, FGMN11, FLOR15, FLM^{+}21, HHM20, IN19, JM15, JLR21, KS12, Kom18, KMW16, LW20, LW22, Pur11]. Product [GS20, LV18, PS20]. Products [Lut21, RR19]. Program [DKS19, KS15]. Programming [Juk20, KPW20, Wil13]. Programs [AFS^{+}18, CMW^{+}12, CM23, GV20, IN19, KNST19, KNS20, DP19, TZ15]. Projective [DKS19]. Promise [BWZ21]. Proof [BCJ19, BHP20, CFM14, Che17, GM15, IOO21, KLMS16, Raz09]. Proofs [Lau16, PV12a, Vio19, Wil13, Yin10, BDK^{+}13]. Properties [Bla19, LS21, NS16]. Property [BC18, PRV18]. Proposed [CEMT14]. Protocols [BKM18, CM23, Fol23, KRU19]. Pseudorandom [AS17, CKLM20, GV20]. Pseudorandomness [Vio19]. PSPACE [BFLW22]. PSPACE-complete [BFLW22].

QBF [BCJ19, BHP20]. Quadratic [Vio16, Wat20a]. Quantum [AGSU15, HM23, MN22, ORR13, RV15, TKM12]. quasi [FJ14]. quasi-orders [FJ14]. Qubits [OS18]. Queries [CM15, RT16]. Query [BSHLM09, BG17, Cha18, GM12, GR09, RRS^{+}12, Smy11].

Ramsey [Lau16]. Random [HSS21]. Randomized [DPV09, GJPW18]. Randomness [HPV11]. Rank [KNST19, KMS16, Lau16, BMT21, SS22]. Rate [AA20]. Ratio [Cha18]. Reachability [BTV09, CT18, KV10]. Read [AFS^{+}18, FGL16, IN19, KNS20, MV18, RR19, Vol16, BH12]. Read- [AFS^{+}18]. Read-Once [FGL16, IN19, MV18, Vol16, KNS20, RR19]. Read/ [BH12]. Real [RV13, Val14]. Reals [OWZ15]. Reasons [BHP20]. Reconstruction [KNST19, MV18]. Reducible [CTW13]. Reduction [KV10]. Reductions [BCG19, DL21, Wat12]. Reed [STV20]. Reflexive [LMP19]. regular [Vid13]. rejection [ORR13]. Related [AH19, FLM^{+}21, KS12]. Relation [GdHKS20]. Relational [FZ16]. Relative [FJK^{+}16]. Relativization [AB18, AB19]. Relativized [Wat12]. Relaxations [TZ18]. Relaxed [GGK19]. Relevant [RT13]. Repetition [PV12a]. Representations [DP19]. Represented [ESY14, SV12]. Require [GM12, Vio19]. Resilient [LPRV22]. Resistant [PV12b]. Resolution [BCJ19, GTT20]. Resolution-Based [BCJ19]. Results [AOTW14, CKP^{+}14, DK13, DM13, FMMS20]. Retractions [FGZ20]. rigid [VK22]. ROABPs [KNS20]. Robber [GTT20]. Robust [DK13]. Roommates [GMSZ21]. Roots [KS12]. Rope [MYKM21]. Round [PV12a]. Routing [HS10]. Running [Kom18].

Samplable [DW12]. Sample [GR16, RR22, Vio16]. Sample-Based [GR16, RR22]. Samples [BC18]. Sampling [GW20, RT16, ORR13]. SAT [BWZ21, LW20, LW22]. Satisfaction [FGL16, JLR21]. Satisfiability [DK13]. Schemes [DSS17]. Science [AG14, AG13]. SDP [TZ18]. Search [HHM20]. Secret [AA20]. Seed [AS17]. Seen [BZ20]. Selection [BFGS23, Cha18]. Selfish [HS10]. Semirings [GHKL18]. Sensitive [OWZ14]. Sensitivity [LS21]. Separate [FJK^{+}16]. Separating [HSS21]. Separation [CKP^{+}14, KNS20, Sri20]. Separations [DPV09]. Set [ALMS18, MN22, PS20, RT16, Zeh23]. Sets [GHPT14, GW20, LL18, NS16, FJ14]. Setting [GMSZ21]. Sharing [AA20]. Side [BZ20]. Sided [RR22]. Sign [BMT21]. Sign-rank [BMT21]. Signal [BBDL^{+}21]. signaling [CMS20]. Simple [Raz09]. Simulations [Wat20a]. Simultaneous [ALMS18]. Size [AS17, DKS19, FZ16, HR16, KS15, RT16]. Skywalker [MYKM21]. Sleeping [KS14]. Slice [FKMW18]. Small [KLMS16, Sch17, VK22]. Smoothed [BM15]. Solution [Sch17]. Solutions [FGMN11, PV12b, SZ14]. Solvable [AT11, Ros20]. Solvable-Group [Ros20]. Solving [GR09]. Some [JP19, JM15]. Sound [BSHLM09]. Source [Che17]. Sources [DW12]. Space [BTV09, CT18, CM15, DLN^{+}22, GJL^{+}16, HM23, PW18b]. Space-Efficient [GJL^{+}16]. Sparse [GR09, HR16]. Sparsification [CJO^{+}23, JP19, LW20]. Spatial [GL18]. Special [AG14, AG13]. Spin [GGS21, GL18]. Split [ALSZ19]. Square [GGR16, KS12]. Square-Free [GGR16]. Stability [DM13]. State [GS18]. Statistical [Wat18]. Steiner [FM23]. Stochastic [VLB12]. Story [ALSZ19]. Strategies [CMS20]. Streaming [BKM18].

Streams [BH12]. String [IOO21]. Strings [Sch17]. Strip [AKPP17]. Strong [GGK19]. Strongly [Sri20]. Structural [NS16, PW18b]. Structure [AJR16, LW22]. Subexponential [DFPV15]. Subgraph [GR20]. Subgraphs [Hav19, KPRR14]. Sublinear [LPRV22]. Sublinear-Time [LPRV22]. Submodular [BCE^{+}19]. Subsequence [RR22]. Subsequence-Freeness [RR22]. Subset [GJL^{+}16]. Succinctly [ESY14]. Sum [GJL^{+}16, KS12, RR19]. Superpolynomial [FPS15]. Surjective [FUZ19, LMP19]. Symmetric [BHLV19]. Symmetrization [Kre21]. Systems [BHP20, CFM14, GGS21, GM15, GL18, GR09, KLMS16].

Terminal [PW18a]. Testability [IY18]. Testable [GGK19]. Testers [GR16]. Testing [AFS^{+}18, BC18, BCG19, BCE^{+}19, CMS20, FGL16, GS20, GR20, MV18, PRV18, RR22]. Tests [BHLV19, LV18]. Their [BCJ19]. Theorem [yCG21, FGST22, GL19, GS20, PV12a, Wat14, Wat20b, Lau16, Raz09]. Theoretical [AG14, AG13]. Theory [AW09, BM15, KC12]. Three [GM12, KNS20]. Three-Query [GM12]. Threshold [CHIS12]. Tight [BłKP^{+}19, FLM^{+}21, KPW20, Kom18]. Time [CT18, HM23, HSS21, JLR21, Kom18, LPRV22, Vid13, Zeh23]. Time-Space [HM23]. Tiny [OWZ14]. Tolerant [BCE^{+}19]. Total [AKP^{+}21]. Tractability [CL17]. Tractable [FFL^{+}13, FHRS16, LW20]. Tradeoff [HM23]. Tradeoffs [HS10]. Trading [Wil13]. Transform [Ail16]. Transformations [FLOR15]. Tree [CMW^{+}12, ES17, GL19, GJ14, IN19, Kre21]. Trichotomy [GGJ17]. Tseitin [GTT20]. Type [yCG21].

UL [DSS17]. Unambiguous [BTV09]. uncertainty [Dru13]. Understanding [Che17]. Uniform [AA20, Bla19, GM15, LS21]. Unifying [AB18, AB19]. Unions [GHPT14]. Unique [DKLM10]. Uniqueness [GL18]. Universal [BBDL^{+}21, GL19]. Unordered [RW20]. Unpredictability [Vio21]. Untold [ALSZ19]. useful [FJ14]. usefulness [AH13]. Useless [Juk20]. Using [Chi21, FLOR15, JP19, RT16, BC18, DKS19, KPRR14].

Valiant [AJR16]. Value [BH12, CFL14]. Valued [FUZ19, TZ18]. Variables [FMMS20, RT13]. Variants [CLV21, STV20]. Verification [PV12b]. Verifying [BDK^{+}13]. versus [BHLV19, DSS17, GJPW18, HHM20]. Vertex [ALMS18, AFK^{+}22, FGMN11, Kom18]. via [BCG19, DM13, Kre21, KMS16, LW20, Lut21]. VNP [Hru16, Sri20]. VNP-Completeness [Hru16]. VP [Sri20]. vs [Cha18].

Way [CEMT14]. Weakly [Bla19]. Weakness [OS18]. Weighing [Pur11]. Weight [HV22]. Weighted [FZ16, Zeh23]. Weighting [DSS17]. Well [Ail16]. Width [ES17]. without [BGV14, Wat12]. Word [BFLW22]. Working [PW18b]. Worlds [Wat12]. Worst [ST19, Wat12]. Worst-Case [Wat12, ST19]. Write [BH12].

XOR [RV15].

Yielding [PV12b].

ZPP [Wat20b].

References

Applebaum:2020:PAS

[AA20] Benny Applebaum and Barak Arkis. On the power of amortization in secret sharing: d-uniform secret sharing and CDS with constant information rate. ACM Transactions on Computation Theory, 12(4):24:1–24:21, December 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3417756.

Aydinlioglu:2018:ARU

[AB18] Baris Aydinlioglu and Eric Bach.

Affine relativization: Unifying the algebrization and relativization barriers. ACM Transactions on Computation Theory, 10(1): 1:1–1:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Aydinlioglu:2019:CAR

[AB19] Baris Aydinlioglu and Eric Bach.

Corrigendum to affine relativization: Unifying the algebrization and relativization barriers. ACM Transactions on Computation Theory, 11(3):16:1– 16:??, June 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https:/

/dl.acm.org/ft_gateway.cfm?
id=3317693.

Ada:2014:HBP

[ACC^{+}14] Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, and Toniann Pitassi. The hardness of being private. ACM Transactions on Computation Theory, 6 (1):1:1–1:??, March 2014. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Arunachalam:2021:IBF

[ACK^{+}21] Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald De Wolf. Improved bounds on Fourier entropy and minentropy. ACM Transactions on Computation Theory, 13(4):22:1– 22:40, December 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3470860.

Arvind:2022:PCF

[AFK^{+}22] Vikraman Arvind, Frank Fuhlbrueck, Johannes Koebler, Sebastian Kuhnert, and Gaurav Rattan. The parameterized complexity of fixing number and vertex individualization in graphs. ACM Transactions on Computation Theory, 14(2):9:1–9:??, June 2022. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3558077.

Anderson:2018:ITL

[AFS^{+}18] Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity testing and lower bounds for read-k oblivious algebraic branching programs. ACM Transactions on Computation Theory, 10(1):3:1– 3:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Allender:2013:ISI

[AG13] Eric Allender and Shafi Goldwasser. Introduction to the special issue on innovations in theoretical computer science 2012. ACM Transactions on Computation Theory, 5(3):8:1–8:??, August 2013. ISSN 1942-3454 (print), 1942-3462 (electronic). Special issue on innovations in theoretical computer science 2012.

Allender:2014:ISI

[AG14] Eric Allender and Shafi Goldwasser. Introduction to the special issue on innovations in theoretical computer science 2012 — Part II. ACM Transactions on Computation Theory, 6(3):10:1– 10:??, July 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Ambainis:2015:LBD

[AGSU15] Andris Ambainis, William Gasarch, Aravind Srinivasan, and Andrey Utis. Lower bounds on the deterministic and quantum communication complexity of Hammingdistance problems. ACM Transactions on Computation Theory, 7(3):10:1–10:??, July 2015. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Austrin:2013:UP

[AH13] Per Austrin and Johan Håstad.

On the usefulness of predicates.

ACM Transactions on Computation Theory, 5(1):1:1–1:??, May 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Allender:2019:NIN

[AH19] Eric Allender and Shuichi Hirahara. New insights on the (non-)Hardness of circuit minimization and related problems. ACM Transactions on Computation Theory, 11(4):27:1–27:??, September 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https:/

                                        /dl.acm.org/ft_gateway.cfm?
                                        id=3349616.

Ailon:2016:OLR

[Ail16] Nir Ailon. An Ω((n log n)/R) lower bound for Fourier transform computation in the R-well conditioned model. ACM Transactions on Computation Theory, 8(1):4:1–4:??, February 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Awasthi:2014:LLF

[AJMR14] Pranjal Awasthi, Madhav Jha, Marco Molinaro, and Sofya Raskhodnikova. Limitations of local filters of Lipschitz and monotone functions. ACM Transactions on Computation Theory, 7(1):2:1–2:??, December 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Arvind:2016:NVC

[AJR16] V. Arvind, P. S. Joglekar, and S. Raja. Noncommutative Valiant’s classes: Structure and complete problems. ACM Transactions on Computation Theory, 9(1):3:1–3:??, December 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Ambainis:2021:ACA

[AKP^{+}21] Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs, and Aleksejs Zajakins. All classical adversary methods are equivalent for total functions. ACM Transactions on Computation Theory, 13(1):7:1–7:20, March 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3442357.

Adamaszek:2017:HAS

[AKPP17] Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, and Michal Pilipczuk. Hardness of approximation for strip packing. ACM Transactions on Computation Theory, 9(3):14:1–14:??, October 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Agrawal:2018:SFV

[ALMS18] Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous feedback vertex set: a parameterized perspective. ACM Transactions on Computation Theory, 10(4):18:1–18:??, October 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Agrawal:2019:SCU

[ALSZ19] Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. ACM Transactions on Computation Theory, 11 (3):18:1–18:??, June 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/ft_
                                        gateway.cfm?id=3319909.

Austrin:2014:NNH

[AOTW14] Per Austrin, Ryan O’Donnell, Li-Yang Tan, and John Wright. New NP-hardness results for 3coloring and 2-to-1 label cover. ACM Transactions on Computation Theory, 6(1):2:1–2:??, March 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Artemenko:2017:PGO

[AS17] Sergei Artemenko and Ronen Shaltiel. Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits. ACM Transactions on Computation Theory, 9(2):6:1– 6:??, May 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Arvind:2011:SGI

[AT11] Vikraman Arvind and Jacobo Torán. Solvable group isomorphism is (almost) in NP ∩ coNP. ACM Transactions on Computation Theory, 2(2):4:1–4:??, March 2011. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Aviv:2019:ELG

[ATS19] Nir Aviv and Amnon Ta-Shma.

On the entropy loss and gap of condensers. ACM Transactions on Computation Theory, 11 (3):15:1–15:??, June 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3317691.

Aaronson:2009:ANB

[AW09] Scott Aaronson and Avi Wigderson. Algebrization: a new barrier in complexity theory. ACM Transactions on Computation Theory, 1(1):2:1–2:??, February 2009. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Becker:2021:AGC

[BBDL^{+}21] Florent Becker, Tom Besson, Jérôme Durand-Lose, Aurélien Emmanuel, Mohammad-Hadi Foroughmand-Araabi, Sama Goliaei, and Shahrzad Heydarshahi. Abstract geometrical computation 10: an intrinsically universal family of signal machines. ACM Transactions on Computation Theory, 13(1):4:1–4:31, March 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/10.1145/3442359.

Bhattacharyya:2018:PTJ

[BC18] Rishiraj Bhattacharyya and Sourav Chakraborty. Property testing of joint distributions using conditional samples. ACM Transactions on Computation Theory, 10(4):16:1–16:??, October 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Blais:2019:TJT

[BCE^{+}19] Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, and Dana Ron. Tolerant junta testing and the connection to submodular optimization and function isomorphism. ACM Transactions on Computation Theory, 11(4):24:1– 24:??, September 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3337789.

Blais:2019:DTL

[BCG19] Eric Blais, Clément L. Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory, 11(2):6:1– 6:??, April 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https:/

/dl.acm.org/ft_gateway.cfm?
id=3305270.

Beyersdorff:2019:NRB

[BCJ19] Olaf Beyersdorff, Leroy Chew, and Mikolás Janota. New resolution-based QBF calculi and their proof complexity. ACM Transactions on Computation Theory, 11(4):26:1–26:??, September 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https:/

/dl.acm.org/ft_gateway.cfm?
id=3352155.

Bliznets:2018:HAF

[BCKP18] Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk. Hardness of approximation for H-free edge modification problems. ACM Transactions on Computation Theory, 10 (2):9:1–9:??, May 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Beyersdorff:2013:VPC

[BDK^{+}13] Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, and Heribert Vollmer. Verifying proofs in constant depth. ACM Transactions on Computation Theory, 5(1):2:1– 2:??, May 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Bandyapadhyay:2023:PCF

[BFGS23] Sayan Bandyapadhyay, Fedor V.

Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized complexity of feature selection for categorical data clustering. ACM Transactions on Computation Theory, 15(3–4): 7:1–7:??, December 2023. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3604797.

Bartholdi:2022:GAH

[BFLW22] Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß. Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems. ACM Transactions on Computation Theory, 14(3–4):11:1–11:??, December 2022. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3569708.

Bhattacharyya:2017:LBC

[BG17] Arnab Bhattacharyya and Sivakanth Gopi. Lower bounds for constant query affine-invariant LCCs and LTCs. ACM Transactions on Computation Theory, 9(2): 7:1–7:??, May 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Bezakova:2021:CAM

[BGGS21] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic. The complexity of approximating the matching polynomial in the complex plane. ACM Transactions on Computation Theory, 13(2): 13:1–13:37, June 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3448645.

Beyersdorff:2012:PBD

[BGLR12] Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, and Alexander A. Razborov. Parameterized bounded-depth Frege is not optimal. ACM Transactions on Computation Theory, 4(3):7:1– 7:??, September 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Beame:2016:NAF

[BGMS16] Paul Beame, Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. Nondeterminism and an abstract formulation of Neciporuk’s lower bound method. ACM Transactions on Computation Theory, 9(1):5:1–5:??, December 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Brakerski:2014:LFH

[BGV14] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory, 6(3):13:1–13:??, July 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Beame:2012:VMR

[BH12] Paul Beame and Trinh Huynh.

The value of multiple Read/ write streams for approximating frequency moments. ACM Transactions on Computation Theory, 3 (2):6:1–6:??, January 2012. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Boppana:2019:BIV

[BHLV19] Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded independence versus symmetric tests. ACM Transactions on Computation Theory, 11(4):21:1–21:??, September 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic).  URL https://dl.
                                        acm.org/ft_gateway.cfm?id=
                                        3337783.

Beyersdorff:2020:RHQ

[BHP20] Olaf Beyersdorff, Luke Hinde, and Ján Pich. Reasons for hardness in QBF proof systems. ACM Transactions on Computation Theory, 12(2):10:1–10:27, May 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic). URL https://dl.acm.
                                        org/doi/abs/10.1145/3378665.

Beame:2010:FCD

[BIPS10] Paul Beame, Russell Impagliazzo, Toniann Pitassi, and Nathan Segerlind. Formula caching in DPLL. ACM Transactions on Computation Theory, 1(3):9:1– 9:??, March 2010. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Boczkowski:2018:SCP

[BKM18] Lucas Boczkowski, Iordanis Kerenidis, and Frédéric Magniez. Streaming communication protocols. ACM Transactions on Computation Theory, 10(4):19:1– 19:??, October 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Bogdanov:2013:HFL

[BKT13] Andrej Bogdanov, Akinori Kawachi, and Hidetoki Tanaka. Hard functions for low-degree polynomials over prime fields. ACM Transactions on Computation Theory, 5 (2):5:1–5:??, July 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Black:2019:MPU

[Bla19] Timothy Black. Monotone properties of k-uniform hypergraphs are weakly evasive. ACM Transactions on Computation Theory, 11(3):14:1–14:??, June 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3313908.

Bonamy:2019:TLB

[BłKP^{+}19] Marthe Bonamy, łUkasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, and Marcin Wrochna. Tight lower bounds for the complexity of multicoloring. ACM Transactions on Computation Theory, 11(3):13:1–13:??, June 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic).  URL https://dl.
acm.org/ft_gateway.cfm?id=
3313906.

Blaser:2015:SCT

[BM15] Markus Bläser and Bodo Manthey. Smoothed complexity theory. ACM Transactions on Computation Theory, 7(2):6:1– 6:??, May 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Bun:2021:SRC

[BMT21] Mark Bun, Nikhil S. Mande, and Justin Thaler. Sign-rank can increase under intersection. ACM Transactions on Computation Theory, 13(4):24:1–24:17, December 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

                                        acm.org/doi/10.1145/3470863.

Ben-Sasson:2009:SQP

[BSHLM09] Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, and Arie Matsliah. Sound 3-query PCPPs are long. ACM Transactions on Computation Theory, 1(2):7:1– 7:??, September 2009. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Bourke:2009:DPR

[BTV09] Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Transactions on Computation Theory, 1(1):4:1–4:??, February 2009. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Brandts:2021:CPS

[BWZ21] Alex Brandts, Marcin Wrochna, and Stanislav Zivný. The complexity of promise SAT on non-Boolean domains. ACM Transactions on Computation Theory, 13(4):26:1–26:20, December 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        10.1145/3470867.

Bulatov:2020:ACC

[BZ20] Andrei A. Bulatov and Stanislav Zivný. Approximate counting CSP seen from the other side. ACM Transactions on Computation Theory, 12(2):11:1– 11:19, May 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://

dl.acm.org/doi/abs/10.1145/
3389390.

Cook:2014:OWF

[CEMT14] James Cook, Omid Etesami, Rachel Miller, and Luca Trevisan. On the one-way function candidate proposed by Goldreich. ACM Transactions on Computation Theory, 6(3):14:1– 14:??, July 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Cook:2014:CCC

[CFL14] Stephen A. Cook, Yuval Filmus, and Dai Tri Man Lê. The complexity of the comparator circuit value problem. ACM Transactions on Computation Theory, 6 (4):15:1–15:??, August 2014. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chen:2014:HIA

[CFM14] Yijia Chen, Jörg Flum, and Moritz Müller. Hard instances of algorithms and proof systems. ACM Transactions on Computation Theory, 6(2):7:1–7:??, May 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chang:2018:MMS

[Cha18] Ching-Lueh Chang. Metric 1median selection: Query complexity vs. approximation ratio.

ACM Transactions on Computation Theory, 9(4):20:1–20:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chen:2017:PCM

[Che17] Hubie Chen. Proof complexity modulo the polynomial hierarchy: Understanding alternation as a source of hardness. ACM Transactions on Computation Theory, 9(3):15:1–15:??, October 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chillara:2021:CMP

[Chi21] Suryajith Chillara. On computing multilinear polynomials using multi-r-ic depth four circuits. ACM Transactions on Computation Theory, 13(3):16:1– 16:21, September 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        10.1145/3460952.

Cheraghchi:2012:ALT

[CHIS12] Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, and Ola Svensson. Approximating linear threshold predicates. ACM Transactions on Computation Theory, 4(1):2:1–2:??, March 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chen:2023:SLB

[CJO^{+}23] Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzażewski. Sparsification lower bounds for list H-coloring. ACM Transactions on Computation Theory, 15(3–4): 8:1–8:??, December 2023. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3612938.

Caragiannis:2016:LDA

[CKK16] Ioannis Caragiannis, Christos Kaklamanis, and Maria Kyropoulou. Limitations of deterministic auction design for correlated bidders. ACM Transactions on Computation Theory, 8(4): 13:1–13:??, July 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Cheraghchi:2020:CLB

[CKLM20] Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. Circuit lower bounds for MCSP from local pseudorandom generators. ACM Transactions on Computation Theory, 12(3):21:1–21:27, July 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/abs/10.1145/3404860.

Cygan:2014:CCG

[CKP^{+}14] Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström. Clique cover and graph separation: New incompressibility results. ACM Transactions on Computation Theory, 6(2):6:1–6:??, May 2014.

CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Cai:2019:GAG

[CKW19] Jin-Yi Cai, Michael Kowalczyk, and Tyson Williams. Gadgets and anti-gadgets leading to a complexity dichotomy. ACM Transactions on Computation Theory, 11(2):7:1–7:??, April 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic).  URL https://dl.
                                        acm.org/ft_gateway.cfm?id=
                                        3305272.

Case:2015:MD

[CL15] Adam Case and Jack H. Lutz. Mutual dimension. ACM Transactions on Computation Theory, 7(3):12:1–12:??, July 2015. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chen:2017:AMC

[CL17] Hubie Chen and Benoit Larose. Asking the metaquestions in constraint tractability. ACM Transactions on Computation Theory, 9(3):11:1–11:??, October 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chaugule:2021:VHP

[CLV21] Prasad Chaugule, Nutan Limaye, and Aditya Varre. Variants of homomorphism polynomials complete for algebraic complexity classes. ACM Transactions on Computation Theory, 13(4):21:1– 21:26, December 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3470858.

Chen:2015:FCC

[CM15] Hubie Chen and Moritz Müller.

The fine classification of conjunctive queries and parameterized logarithmic space. ACM Transactions on Computation Theory, 7(2):7:1–7:??, May 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Cote:2023:CBP

[CM23] Hugo Côté and Pierre McKenzie. Catalytic branching programs from groups and general protocols. ACM Transactions on Computation Theory, 15(3–4): 5:1–5:??, December 2023. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3583085.

Chiesa:2020:TLA

[CMS20] Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Testing linearity against non-signaling strategies. ACM Transactions on Computation Theory, 12(3):16:1– 16:51, July 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://

dl.acm.org/doi/abs/10.1145/
3397474.

Cook:2012:PBP

[CMW^{+}12] Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam. Pebbles and branching programs for tree evaluation. ACM Transactions on Computation Theory, 3(2): 4:1–4:??, January 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Cygan:2013:MCP

[CPPW13] Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. ACM Transactions on Computation Theory, 5(1):3:1– 3:??, May 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chatterjee:2023:CFH

[CS23] Prerona Chatterjee and Ramprasad Saptharishi. Constructing faithful homomorphisms over fields of finite characteristic. ACM Transactions on Computation Theory, 15(1–2):1:1–1:??, June 2023. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

                                        acm.org/doi/10.1145/3580351.

Chakraborty:2018:SPT

[CT18] Diptarka Chakraborty and Raghunath Tewari. An O(nϵ) space and polynomial time algorithm for reachability in directed layered planar graphs. ACM Transactions on Computation Theory, 9(4):19:1–19:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Chattopadhyay:2013:GIA

[CTW13] Arkadev Chattopadhyay, Jacobo Torán, and Fabian Wagner. Graph isomorphism is not AC^{0}-reducible to group isomorphism. ACM Transactions on Computation Theory, 5(4):13:1– 13:??, November 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Drange:2015:ESC

[DFPV15] Pål Grønås Drange, Fedor V.

Fomin, Michal Pilipczuk, and Yngve Villanger. Exploring the subexponential complexity of completion problems. ACM Transactions on Computation Theory, 7(4):14:1–14:??, September 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Dalmau:2013:RSC

[DK13] Víctor Dalmau and Andrei Krokhin. Robust satisfiability for CSPs: Hardness and algorithmic results. ACM Transactions on Computation Theory, 5(4):15:1– 15:??, November 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Datta:2010:PDP

[DKLM10] Samir Datta, Raghav Kulkarni, Nutan Limaye, and Meena Mahajan. Planarity, determinants, permanents, and (unique) matchings. ACM Transactions on Computation Theory, 1(3):10:1– 10:??, March 2010. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Dinesh:2019:CLB

[DKS19] Krishnamoorthy Dinesh, Sajin Koroth, and Jayalal Sarma.

Characterization and lower bounds for branching program size using projective dimension. ACM Transactions on Computation Theory, 11(2):8:1–8:??, April 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic).  URL https://dl.
acm.org/ft_gateway.cfm?id=
3305274.

Dell:2021:FGR

[DL21] Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to decision. ACM Transactions on Computation Theory, 13(2):8:1–8:24, June 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/10.1145/3442352.

Datta:2022:PGI

[DLN^{+}22] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. ACM Transactions on Computation Theory, 14 (2):8:1–8:??, June 2022. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3543686.

De:2013:EOH

[DM13] Anindya De and Elchanan Mossel. Explicit optimal hardness via Gaussian stability results. ACM Transactions on Computation Theory, 5(4):14:1–14:??, November 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Oliveira:2019:RMB

[DP19] Mateus De Oliveira Oliveira and Pavel Pudlák. Representations of monotone Boolean functions by linear programs. ACM Transactions on Computation Theory, 11 (4):22:1–22:??, September 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3337787.

David:2009:ISB

[DPV09] Matei David, Toniann Pitassi, and Emanuele Viola. Improved separations between nondeterministic and randomized multiparty communication. ACM Transactions on Computation Theory, 1(2):5:1–5:??, September 2009. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Drucker:2013:HCP

[Dru13] Andrew Drucker. High-confidence predictions under adversarial uncertainty. ACM Transactions on Computation Theory, 5(3):12:1– 12:??, August 2013. ISSN 1942-3454 (print), 1942-3462 (electronic). Special issue on innovations in theoretical computer science 2012.

Dhayal:2017:MMP

[DSS17] Anant Dhayal, Jayalal Sarma, and Saurabh Sawlani. Min/maxpoly weighting schemes and the NL versus UL problem. ACM Transactions on Computation Theory, 9(2):10:1–10:??, May 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

De:2012:ELB

[DW12] Anindya De and Thomas Watson. Extractors and lower bounds for locally samplable sources. ACM Transactions on Computation Theory, 4(1):3:1–3:??, March 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Englert:2013:EC

[ERSV13] Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking. Economical caching. ACM Transactions on Computation Theory, 5(2):4:1–4:??, July 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Elberfeld:2017:CGB

[ES17] Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. ACM Transactions on Computation Theory, 9(3):12:1–12:??, October 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Etessami:2014:NCC

[ESY14] Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis. A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. ACM Transactions on Computation Theory, 6(2):9:1–9:??, May 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fellows:2013:DFP

[FFL^{+}13] Michael Fellows, Fedor V.

Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances Rosamond, and Saket Saurabh. Distortion is fixed parameter tractable. ACM Transactions on Computation Theory, 5(4):16:1–16:??, November 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fischer:2016:TRO

[FGL16] Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish. Testing read-once formula satisfaction. ACM Transactions on Computation Theory, 8(2):5:1– 5:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fellows:2011:CDF

[FGMN11] Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier. A complexity dichotomy for finding disjoint solutions of vertex deletion problems. ACM Transactions on Computation Theory, 2(2):5:1–5:??, March 2011. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fomin:2022:AMT

[FGST22] Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. An algorithmic meta-theorem for graph modification to planarity and FOL. ACM Transactions on Computation Theory, 14(3–4): 13:1–13:??, December 2022. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3571278.

Focke:2020:CAC

[FGZ20] Jacob Focke, Leslie Ann Goldberg, and Stanislav Zivný. The complexity of approximately counting retractions. ACM Transactions on Computation Theory, 12(3):15:1–15:43, July 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/abs/10.1145/3397472.

Fellows:2016:TPM

[FHRS16] Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Hadas Shachnai. Tractable parameterizations for the minimum linear arrangement problem. ACM Transactions on Computation Theory, 8(2):6:1– 6:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fellows:2014:FCU

[FJ14] Michael R. Fellows and Bart M. P. Jansen. FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders. ACM Transactions on Computation Theory, 6 (4):16:1–16:??, August 2014. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fontes:2016:RDD

[FJK^{+}16] Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, and Jérémie Roland. Relative discrepancy does not separate information and communication complexity. ACM Transactions on Computation Theory, 9(1):4:1–4:??, December 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Filmus:2018:IPS

[FKMW18] Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. Invariance principle on the slice. ACM Transactions on Computation Theory, 10(3):11:1– 11:??, June 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fomin:2021:CHN

[FLM^{+}21] Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of Hadwiger number and related contraction problems: Tight lower bounds. ACM Transactions on Computation Theory, 13(2):10:1–10:25, June 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/10.1145/3448639.

Fernau:2015:UPT

[FLOR15] Henning Fernau, Alejandro López-Ortiz, and Jazmín Romero. Using parametric transformations toward polynomial kernels for packing problems allowing overlaps. ACM Transactions on Computation Theory, 7(3):13:1– 13:??, July 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Feldmann:2023:CLF

[FM23] Andreas Emil Feldmann and Dániel Marx. The complexity landscape of fixed-parameter directed Steiner network problems. ACM Transactions on Computation Theory, 15(3–4): 4:1–4:??, December 2023. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3580376.

Fernau:2020:PMV

[FMMS20] Henning Fernau, Florin Manea, Robert Mercas, and Markus L. Schmid. Pattern matching with variables: Efficient algorithms and complexity results. ACM Transactions on Computation Theory, 12(1):6:1–6:37, February 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/abs/10.1145/3369935.

Folwarczny:2023:PMF

[Fol23] Lukás Folwarczný. On protocols for monotone feasible interpolation. ACM Transactions on Computation Theory, 15(1– 2):2:1–2:??, June 2023. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3583754.

Fortnow:2009:EF

[For09] Lance Fortnow. Editor’s foreword. ACM Transactions on Computation Theory, 1(1):1:1– 1:??, February 2009. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Filmus:2015:ELB

[FPS15] Yuval Filmus, Toniann Pitassi, and Rahul Santhanam. Exponential lower bounds for AC0-Frege imply superpolynomial Frege lower bounds. ACM Transactions on Computation Theory, 7 (2):5:1–5:??, May 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Fulla:2019:CBS

[FUZ19] Peter Fulla, Hannes Uppman, and Stanislav Zivný. The complexity of Boolean surjective general-valued CSPs. ACM Transactions on Computation Theory, 11(1):4:1–4:??, January 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic).  URL https://dl.
acm.org/ft_gateway.cfm?id=
3282429.

Fulla:2016:GCW

[FZ16] Peter Fulla and Stanislav Zivný.

A Galois connection for weighted (relational) clones of infinite size. ACM Transactions on Computation Theory, 8(3):9:1–9:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Ganian:2020:EMR

[GdHKS20] Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider. On existential MSO and its relation to ETH. ACM Transactions on Computation Theory, 12(4):22:1–22:32, December 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3417759.

Galanis:2017:CTA

[GGJ17] Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. A complexity trichotomy for approximately counting list Hcolorings. ACM Transactions on Computation Theory, 9(2): 9:1–9:??, May 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Goldreich:2019:SLT

[GGK19] Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong locally testable codes with relaxed local decoders. ACM Transactions on Computation Theory, 11 (3):17:1–17:??, June 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3319907.

Gobel:2014:CCH

[GGR14] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Transactions on Computation Theory, 6(4):17:1– 17:??, August 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Gobel:2016:CHS

[GGR16] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting homomorphisms to squarefree graphs, modulo 2. ACM Transactions on Computation Theory, 8(3):12:1–12:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Galanis:2021:FAG

[GGS21] Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast algorithms for general spin systems on bipartite expanders. ACM Transactions on Computation Theory, 13(4): 25:1–25:18, December 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3470865.

Galanis:2022:ICH

[GGW22] Andreas Galanis, Heng Guo, and Jiaheng Wang. Inapproximability of counting hypergraph colourings. ACM Transactions on Computation Theory, 14(3–4):10:1– 10:??, December 2022. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3558554.

Ganardi:2018:CEF

[GHKL18] Moses Ganardi, Danny Hucke, Daniel König, and Markus Lohrey. Circuits and expressions over finite semirings. ACM Transactions on Computation Theory, 10(4):15:1–15:??, October 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Glasser:2014:UDN

[GHPT14] Christian Glaßer, John M. Hitchcock, A. Pavan, and Stephan Travers. Unions of disjoint NPcomplete sets. ACM Transactions on Computation Theory, 6 (1):3:1–3:??, March 2014. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Goldberg:2014:CAC

[GJ14] Leslie Ann Goldberg and Mark Jerrum. The complexity of approximately counting tree homomorphisms. ACM Transactions on Computation Theory, 6(2): 8:1–8:??, May 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Goldberg:2019:APC

[GJ19] Leslie Ann Goldberg and Mark Jerrum. Approximating pairwise correlations in the Ising model. ACM Transactions on Computation Theory, 11(4):23:1– 23:??, September 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/ft_
                                        gateway.cfm?id=3337785.

Gal:2016:SEA

[GJL^{+}16] Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, and Karteek Sreenivasaiah. Spaceefficient approximations for subset sum. ACM Transactions on Computation Theory, 8(4):16:1– 16:??, July 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Gunda:2021:PAC

[GJL^{+}21] Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. On the parameterized approximability of contraction to classes of chordal graphs. ACM Transactions on Computation Theory, 13(4):27:1– 27:40, December 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3470869.

Goos:2018:RCV

[GJPW18] Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication versus partition number. ACM Transactions on Computation Theory, 10(1):4:1–4:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Gurjar:2016:PGP

[GKM^{+}16] Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf. Planarizing gadgets for perfect matching do not exist. ACM Transactions on Computation Theory, 8(4):14:1–14:??, July 2016. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Ghosh:2020:FAE

[GKM20] Arijit Ghosh, Sudeshna Kolay, and Gopinath Mishra. FPT algorithms for embedding into lowcomplexity graphic metrics. ACM Transactions on Computation Theory, 12(1):1:1–1:41, February 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic). URL https://dl.acm.
                                        org/doi/abs/10.1145/3369933.

Gurjar:2017:EPM

[GKMT17] Rohit Gurjar, Arpita Korwar, Jochen Messner, and Thomas Thierauf. Exact perfect matching in complete graphs. ACM Transactions on Computation Theory, 9(2):8:1–8:??, May 2017. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Guo:2018:USM

[GL18] Heng Guo and Pinyan Lu. Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems. ACM Transactions on Computation Theory, 10(4):17:1–17:??, October 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Ganardi:2019:UTB

[GL19] Moses Ganardi and Markus Lohrey. A universal tree balancing theorem. ACM Transactions on Computation Theory, 11 (1):1:1–1:??, January 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/ft_
                                        gateway.cfm?id=3278158.

Gal:2012:TQL

[GM12] Anna Gal and Andrew Mills.

Three-query locally decodable codes with higher correctness require exponential length. ACM Transactions on Computation Theory, 3(2):5:1–5:??, January 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Goldreich:2015:IOP

[GM15] Oded Goldreich and Or Meir.

Input-oblivious proof systems and a uniform complexity perspective on P/poly. ACM Transactions on Computation Theory, 7(4):16:1–16:??, September 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Greco:2014:CNC

[GMPS14] Gianluigi Greco, Enrico Malizia, Luigi Palopoli, and Francesco Scarcello. The complexity of the nucleolus in compact games. ACM Transactions on Computation Theory, 7(1):3:1–3:??, December 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Gupta:2021:PMR

[GMSZ21] Sushmita Gupta, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Popular matching in roommates setting is NP-hard. ACM Transactions on Computation Theory, 13(2):9:1–9:20, June 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/10.1145/3442354.

Guruswami:2009:HSS

[GR09] Venkatesan Guruswami and Prasad Raghavendra. Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers. ACM Transactions on Computation Theory, 1(2):6:1–6:??, September 2009. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Goldreich:2016:SBT

[GR16] Oded Goldreich and Dana Ron. On sample-based testers. ACM Transactions on Computation Theory, 8(2):7:1–7:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Goldreich:2020:STM

[GR20] Oded Goldreich and Dana Ron. The subgraph testing model. ACM Transactions on Computation Theory, 12(4):28:1– 28:32, December 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        10.1145/3428675.

Gharibian:2018:GSC

[GS18] Sevag Gharibian and Jamie Sikora. Ground state connectivity of local Hamiltonians. ACM Transactions on Computation Theory, 10(2):8:1–8:??, May 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Goldenberg:2020:TGD

[GS20] Elazar Goldenberg and Karthik C. S. Toward a general direct product testing theorem. ACM Transactions on Computation Theory, 12(1):7:1–7:18, February 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
abs/10.1145/3369939.

Galesi:2020:CRG

[GTT20] Nicola Galesi, Navid Talebanfard, and Jacobo Torán. Cops– robber games and the resolution of Tseitin formulas. ACM Transactions on Computation Theory, 12(2):9:1–9:22, May 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
abs/10.1145/3378667.

Gurjar:2020:PBO

[GV20] Rohit Gurjar and Ben Lee Volk. Pseudorandom bits for oblivious branching programs. ACM Transactions on Computation Theory, 12(2):8:1–8:12, May 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/abs/10.1145/3378663.

Goos:2020:LBS

[GW20] Mika Göös and Thomas Watson. A lower bound for sampling disjoint sets. ACM Transactions on Computation Theory, 12(3):20:1–20:13, July 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
abs/10.1145/3404858.

Haviv:2019:MFS

[Hav19] Ishay Haviv. On minrank and forbidden subgraphs. ACM Transactions on Computation Theory, 11(4):20:1–20:??, September 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic).  URL https://dl.
                                        acm.org/ft_gateway.cfm?id=
                                        3322817.

Harkins:2013:ELA

[HH13] Ryan C. Harkins and John M. Hitchcock. Exact learning algorithms, betting games, and circuit lower bounds. ACM Transactions on Computation Theory, 5(4):18:1–18:??, November 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Hemaspaandra:2020:SVD

[HHM20] Edith Hemaspaandra, Lane A. Hemaspaandra, and Curtis Menton. Search versus decision for election manipulation problems. ACM Transactions on Computation Theory, 12(1):3:1– 3:42, February 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        abs/10.1145/3369937.

Hamoudi:2023:QTS

[HM23] Yassine Hamoudi and Frédéric Magniez. Quantum time-space tradeoff for finding multiple collision pairs. ACM Transactions on Computation Theory, 15(1– 2):3:1–3:??, June 2023. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3589986.

Hermo:2020:ELB

[HO20] Montserrat Hermo and Ana Ozaki. Exact learning: On the boundary between Horn and CNF. ACM Transactions on Computation Theory, 12(1):4:1– 4:25, February 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL

https://dl.acm.org/doi/abs/
10.1145/3369930.

Hitchcock:2011:KCR

[HPV11] John M. Hitchcock, A. Pavan, and N. V. Vinodchandran. Kolmogorov complexity in randomness extraction. ACM Transactions on Computation Theory, 3 (1):1:1–1:??, August 2011. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Haviv:2016:LDS

[HR16] Ishay Haviv and Oded Regev.

The list-decoding size of Fouriersparse Boolean functions. ACM Transactions on Computation Theory, 8(3):10:1–10:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Hrubes:2016:HMV

[Hru16] P. Hrubes. On hardness of multilinearization and VNPcompleteness in characteristic 2. ACM Transactions on Computation Theory, 9(1):1:1–1:??, December 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Hoefer:2010:TAC

[HS10] Martin Hoefer and Alexander Souza. Tradeoffs and averagecase equilibria in selfish routing. ACM Transactions on Computation Theory, 2(1):2:1–2:??, November 2010. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Hitchcock:2021:PTR

[HSS21] John M. Hitchcock, Adewale Sekoni, and Hadi Shafei. Polynomialtime random oracles and separating complexity classes. ACM Transactions on Computation Theory, 13(1):1:11–1:16, March 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic). URL https://dl.acm.
                                        org/doi/10.1145/3434389.

Huang:2022:ADW

[HV22] Xuangui Huang and Emanuele Viola. Approximate degree, weight, and indistinguishability. ACM Transactions on Computation Theory, 14(1):3:1– 3:26, March 2022. ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic). URL https://doi.org/
                                        10.1145/3492338.

Iwama:2019:ROB

[IN19] Kazuo Iwama and Atsuki Nagao. Read-once branching programs for tree evaluation problems. ACM Transactions on Computation Theory, 11(1):5:1– 5:??, January 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https:/

/dl.acm.org/ft_gateway.cfm?
id=3282433.

Itsykson:2021:CPC

[IOO21] Dmitry Itsykson, Alexander Okhotin, and Vsevolod Oparin. Computational and proof complexity of partial string avoidability. ACM Transactions on Computation Theory, 13(1):6:1–6:25, March 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3442365.

Iwama:2018:PT

[IY18] Kazuo Iwama and Yuichi Yoshida.

Parameterized testability. ACM Transactions on Computation Theory, 9(4):16:1–16:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Jonsson:2021:FGT

[JLR21] Peter Jonsson, Victor Lagerkvist, and Biman Roy. Fine-grained time complexity of constraint satisfaction problems. ACM Transactions on Computation Theory, 13(1):2:1–2:32, March 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3434387.

Jerrum:2015:SHF

[JM15] Mark Jerrum and Kitty Meeks.

Some hard families of parameterized counting problems. ACM Transactions on Computation Theory, 7(3):11:1–11:??, July 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Jansen:2019:OSS

[JP19] Bart M. P. Jansen and Astrid Pieterse. Optimal sparsification for some binary CSPs using lowdegree polynomials. ACM Transactions on Computation Theory, 11(4):28:1–28:??, September 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic).  URL https://dl.
                                        acm.org/ft_gateway.cfm?id=
                                        3349618.

Jukna:2020:CFD

[Juk20] Stasys Jukna. Coin flipping in dynamic programming is almost useless. ACM Transactions on Computation Theory, 12 (3):17:1–17:26, July 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        abs/10.1145/3397476.

Kawamura:2012:CTO

[KC12] Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. ACM Transactions on Computation Theory, 4(2):5:1–5:??, May 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kabanets:2021:ALB

[KKL^{+}21] Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira. Algorithms and lower bounds for De Morgan formulas of lowcommunication leaf gates. ACM Transactions on Computation Theory, 13(4):23:1–23:37, December 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3470861.

Krebs:2016:SDP

[KLMS16] Andreas Krebs, Nutan Limaye, Meena Mahajan, and Karteek Sreenivasaiah. Small depth proof systems. ACM Transactions on Computation Theory, 9(1):2:1– 2:??, December 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kumar:2016:ACL

[KMS16] Mrinal Kumar, Gaurav Maheshwari, and Jayalal Sarma. Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices. ACM Transactions on Computation Theory, 8 (3):8:1–8:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kratsch:2016:PCK

[KMW16] Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized complexity and kernelizability of max ones and exact ones problems. ACM Transactions on Computation Theory, 8 (1):1:1–1:??, February 2016. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kayal:2020:SBR

[KNS20] Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits. ACM Transactions on Computation Theory, 12(1):2:1–2:27, February 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
abs/10.1145/3369928.

Kayal:2019:RFR

[KNST19] Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of full rank algebraic branching programs. ACM Transactions on Computation Theory, 11(1):2:1–2:??, January 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https:/

/dl.acm.org/ft_gateway.cfm?
id=3282427.

Komusiewicz:2018:TRT

[Kom18] Christian Komusiewicz. Tight running time lower bounds for vertex deletion problems. ACM Transactions on Computation Theory, 10(2):6:1–6:??, May 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kratsch:2014:KLB

[KPRR14] Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, and Venkatesh Raman. Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs. ACM Transactions on Computation Theory, 7(1):4:1–4:??, December 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kolay:2019:CCG

[KPS19] Sudeshna Kolay, Fahad Panolan, and Saket Saurabh. Communication complexity and graph families. ACM Transactions on Computation Theory, 11(2): 11:1–11:??, April 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3313234.

Knop:2020:TCL

[KPW20] Dusan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight complexity lower bounds for integer linear programming with few constraints. ACM Transactions on Computation Theory, 12 (3):19:1–19:19, July 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
abs/10.1145/3397484.

Kretschmer:2021:LBT

[Kre21]  William Kretschmer.  Lower

bounding the AND–OR tree via symmetrization. ACM Transactions on Computation Theory, 13 (1):3:1–3:11, March 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3434385.

Kerenidis:2019:MPP

[KRU19] Iordanis Kerenidis, Adi Rosén, and Florent Urrutia. Multi-party protocols, information complexity and privacy. ACM Transactions on Computation Theory, 11(2):9:1–9:??, April 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/ft_
                                        gateway.cfm?id=3313230.

Kayal:2012:SSR

[KS12] Neeraj Kayal and Chandan Saha. On the sum of square roots of polynomials and related problems. ACM Transactions on Computation Theory, 4(4):9:1– 9:??, November 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kanade:2014:LHS

[KS14] Varun Kanade and Thomas Steinke. Learning hurdles for sleeping experts. ACM Transactions on Computation Theory, 6 (3):11:1–11:??, July 2014. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Komarath:2015:PEB

[KS15] Balagopal Komarath and Jayalal Sarma. Pebbling, entropy, and branching program size lower bounds. ACM Transactions on Computation Theory, 7(2):8:1– 8:??, May 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kulkarni:2011:PIP

[Kul11] Raghav Kulkarni. On the power of isolation in planar graphs. ACM Transactions on Computation Theory, 3(1):2:1–2:??, August 2011. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Kumar:2020:PBD

[Kum20] Mrinal Kumar. On the power of border of depth-3 arithmetic circuits. ACM Transactions on Computation Theory, 12(1): 5:1–5:8, February 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
abs/10.1145/3371506.

Kyncl:2010:LRD

[KV10] Jan Kynčl and Tomáš Vyskočil.

Logspace reduction of directed reachability for bounded genus graphs to the planar case. ACM Transactions on Computation Theory, 1(3):8:1–8:??, March 2010. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Lauria:2016:RLB

[Lau16] Massimo Lauria. A rank lower bound for cutting planes proofs of Ramsey’s Theorem. ACM Transactions on Computation Theory, 8(4):17:1–17:??, July 2016. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Lutz:2018:AIP

[LL18] Jack H. Lutz and Neil Lutz.

Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Transactions on Computation Theory, 10(2):7:1– 7:??, May 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Larose:2019:SHC

[LMP19] Benoît Larose, Barnaby Martin, and Daniël Paulusma. Surjective h-colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1): 3:1–3:??, January 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3282431.

Levi:2022:ERS

[LPRV22] Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Erasureresilient sublinear-time graph algorithms. ACM Transactions on Computation Theory, 14(1): 1:1–1:??, March 2022. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3488250.

Li:2021:SCU

[LS21] Qian Li and Xiaoming Sun. On the sensitivity complexity of kuniform hypergraph properties. ACM Transactions on Computation Theory, 13(2):12:1–12:13, June 2021. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3448643.

Lutz:2021:FIP

[Lut21] Neil Lutz. Fractal intersections and products via algorithmic dimension. ACM Transactions on Computation Theory, 13(3):14:1– 14:15, September 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3460948.

Lee:2018:CPP

[LV18] Chin Ho Lee and Emanuele Viola. The coin problem for product tests. ACM Transactions on Computation Theory, 10(3): 14:1–14:??, June 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Lagerkvist:2020:SSC

[LW20] Victor Lagerkvist and Magnus Wahlström. Sparsification of SAT and CSP problems via tractable extensions. ACM Transactions on Computation Theory, 12(2): 13:1–13:29, May 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
abs/10.1145/3389411.

Lagerkvist:2022:CFG

[LW22] Victor Lagerkvist and Magnus Wahlström. The (coarse) finegrained structure of NP-Hard SAT and CSP problems. ACM Transactions on Computation Theory, 14(1):2:1–2:??, March 2022. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/10.1145/3492336.

Magniez:2022:QDC

[MN22] Frédéric Magniez and Ashwin Nayak. Quantum distributed complexity of set disjointness on a line. ACM Transactions on Computation Theory, 14(1):5:1– 5:22, March 2022. ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic). URL https://doi.org/
                                        10.1145/3512751.

Minahan:2018:CDI

[MV18] Daniel Minahan and Ilya Volkovich. Complete derandomization of identity testing and reconstruction of read-once formulas. ACM Transactions on Computation Theory, 10(3):10:1–10:??, June 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Monde:2021:CSL

[MYKM21] Akihiro Monde, Yukiko Yamauchi, Shuji Kijima, and Yamashita Masafumi. Can a skywalker localize the midpoint of a rope? ACM Transactions on Computation Theory, 13(3): 17:1–17:23, September 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        10.1145/3460954.

Nguyen:2016:SPN

[NS16] Dung Nguyen and Alan L. Selman. Structural properties of nonautoreducible sets. ACM Transactions on Computation Theory, 8(3):11:1–11:??, May 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Nakajima:2022:LOC

[NŽ22] Tamio-Vesa Nakajima and Stanislav Živný. Linearly ordered colourings of hypergraphs. ACM Transactions on Computation Theory, 14(3–4):12:1–12:??, December 2022. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3570909.

ODonnell:2020:ENE

[O’D20] Ryan O’Donnell. Editorial from the new Editor-in-Chief. ACM Transactions on Computation Theory, 12(1):1e:1, February 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/abs/10.1145/3381517.

Ozols:2013:QRS

[ORR13] Maris Ozols, Martin Roetteler, and Jérémie Roland. Quantum rejection sampling. ACM Transactions on Computation Theory, 5(3):11:1–11:??, August 2013. ISSN 1942-3454 (print), 1942-3462 (electronic). Special issue on innovations in theoretical computer science 2012.

ODonnell:2018:WCQ

[OS18] Ryan O’Donnell and A. C. Cem Say. The weakness of CTC qubits and the power of approximate counting. ACM Transactions on Computation Theory, 10 (2):5:1–5:??, May 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

ODonnell:2014:OLB

[OWZ14] Ryan O’Donnell, Yi Wu, and Yuan Zhou. Optimal lower bounds for locality-sensitive hashing (except when q is tiny).

ACM Transactions on Computation Theory, 6(1):5:1–5:??, March 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

ODonnell:2015:HMM

[OWZ15] Ryan O’Donnell, Yi Wu, and Yuan Zhou. Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups. ACM Transactions on Computation Theory, 7(2):9:1–9:??, May 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Pagh:2013:CMM

[Pag13] Rasmus Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory, 5(3):9:1–9:??, August 2013. ISSN 1942-3454 (print), 1942-3462 (electronic). Special issue on innovations in theoretical computer science 2012.

Pallavoor:2018:PPT

[PRV18] Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized property testing of functions. ACM Transactions on Computation Theory, 9(4):17:1–17:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Podolskii:2020:IPS

[PS20] Vladimir V. Podolskii and Alexander A. Sherstov. Inner product and set disjointness: Beyond logarithmically many parties. ACM Transactions on Computation Theory, 12(4):26:1– 26:28, December 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3428671.

Purdy:2011:LBC

[Pur11] Eric Purdy. Lower bounds for coin-weighing problems. ACM Transactions on Computation Theory, 2(2):3:1–3:??, March 2011. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Pass:2012:PRT

[PV12a] Rafael Pass and Muthuramakrishnan Venkitasubramaniam. A parallel repetition theorem for constant-round Arthur–Merlin proofs. ACM Transactions on Computation Theory, 4(4):10:1– 10:??, November 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Penna:2012:CRM

[PV12b] Paolo Penna and Carmine Ventre. Collusion-resistant mechanisms with verification yielding optimal solutions. ACM Transactions on Computation Theory, 4 (2):6:1–6:??, May 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Pilipczuk:2018:DMW

[PW18a] Marcin Pilipczuk and Magnus Wahlström. Directed multicut is W [1]-hard, even for four terminal pairs. ACM Transactions on Computation Theory, 10(3):

13:1–13:??, June 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Pilipczuk:2018:SEA

[PW18b] Michal Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. ACM Transactions on Computation Theory, 9(4):18:1–18:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Razborov:2009:SPB

[Raz09] Alexander Razborov. A simple proof of Bazzi’s Theorem. ACM Transactions on Computation Theory, 1(1):3:1–3:??, February 2009. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Rosenbaum:2020:BGE

[Ros20] David J. Rosenbaum. Beating the generator-enumeration bound for solvable-group isomorphism. ACM Transactions on Computation Theory, 12(2): 12:1–12:18, May 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        abs/10.1145/3389396.

Ramya:2019:LBS

[RR19] C. Ramya and B. V. Raghavendra Rao. Lower bounds for sum and sum of products of readonce formulas. ACM Transactions on Computation Theory, 11 (2):10:1–10:??, April 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3313232.

Ron:2022:ODF

[RR22] Dana Ron and Asaf Rosin. Optimal distribution-free samplebased testing of subsequencefreeness with one-sided error. ACM Transactions on Computation Theory, 14(1):4:1–4:??, March 2022. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://dl.

acm.org/doi/10.1145/3512750.

Ron:2012:AIM

[RRS^{+}12] Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, and Omri Weinstein. Approximating the influence of monotone Boolean functions in O(\sqrt{n}) query complexity. ACM Transactions on Computation Theory, 4(4):11:1–11:??, November 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Ron:2013:ANR

[RT13] Dana Ron and Gilad Tsur. On approximating the number of relevant variables in a function. ACM Transactions on Computation Theory, 5(2):7:1–7:??, July 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Ron:2016:PEH

[RT16] Dana Ron and Gilad Tsur. The power of an example: Hidden set size approximation using group queries and conditional sampling. ACM Transactions on Computation Theory, 8(4):15:1– 15:??, July 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Razborov:2013:RA

[RV13] Alexander Razborov and Emanuele Viola. Real advantage. ACM Transactions on Computation Theory, 5(4):17:1–17:??, November 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Regev:2015:QXG

[RV15] Oded Regev and Thomas Vidick. Quantum XOR games. ACM Transactions on Computation Theory, 7(4):15:1–15:??, September 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Rahman:2020:CUC

[RW20] Md Lutfar Rahman and Thomas Watson. Complexity of unordered CNF games. ACM Transactions on Computation Theory, 12(3):18:1–18:18, July 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

                                        tronic). URL https://dl.acm.
                                        org/doi/abs/10.1145/3397478.

Schmitz:2016:CHB

[Sch16]  Sylvain Schmitz.  Complex-

ity hierarchies beyond elementary. ACM Transactions on Computation Theory, 8(1):3:1–3:??, February 2016. CODEN ????

ISSN 1942-3454 (print), 1942-3462 (electronic).

Schmid:2017:FCS

[Sch17] Markus L. Schmid. Finding consensus strings with small length difference between input and solution strings. ACM Transactions on Computation Theory, 9(3): 13:1–13:??, October 2017. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Scheder:2019:PMB

[Sch19] Dominik Scheder. PPSZ for k ≥ 5: More is better. ACM Transactions on Computation Theory, 11 (4):25:1–25:??, September 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/ft_
gateway.cfm?id=3349613.

Smyth:2011:AQC

[Smy11] Clifford Smyth. Approximate query complexity. ACM Transactions on Computation Theory, 3(1):3:1–3:??, August 2011. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Srinivasan:2020:SES

[Sri20] Srikanth Srinivasan. Strongly exponential separation between monotone VP and monotone VNP. ACM Transactions on Computation Theory, 12(4):23:1– 23:12, December 2020. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3417758.

Singer:2022:PHI

[SS22] Noah Singer and Madhu Sudan. Point-hyperplane incidence geometry and the logrank conjecture. ACM Transactions on Computation Theory, 14(2):7:1–7:??, June 2022. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3543684.

Schoenebeck:2019:BWC

[ST19] Grant Schoenebeck and Biaoshuai Tao. Beyond worst-case (in)approximability of nonsubmodular influence maximization. ACM Transactions on Computation Theory, 11(3):12:1– 12:??, June 2019. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https:/

/dl.acm.org/ft_gateway.cfm?
id=3313904.

Srinivasan:2020:DVR

[STV20] Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. Decoding variants of Reed–Muller codes over finite grids. ACM Transactions on Computation Theory, 12(4):25:1–25:11, December 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3417754.

Schoenebeck:2012:CCN

[SV12] Grant R. Schoenebeck and Salil Vadhan. The computational complexity of Nash equilibria in concisely represented games. ACM Transactions on Computation Theory, 4(2):4:1–4:??, May 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Sun:2014:ECN

[SZ14] Shu-Ming Sun and Ning Zhong.

On effective convergence of numerical solutions for differential equations. ACM Transactions on Computation Theory, 6(1): 4:1–4:??, March 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Tani:2012:EQA

[TKM12] Seiichiro Tani, Hirotada Kobayashi, and Keiji Matsumoto. Exact quantum algorithms for the leader election problem. ACM Transactions on Computation Theory, 4(1):1:1–1:??, March 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Teutsch:2015:ADM

[TZ15] Jason Teutsch and Marius Zimand. On approximate decidability of minimal programs. ACM Transactions on Computation Theory, 7(4):17:1–17:??, September 2015. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Thapper:2018:LSR

[TZ18] Johan Thapper and Stanislav Zivný. The limits of SDP relaxations for general-valued CSPs. ACM Transactions on Computation Theory, 10(3):12:1– 12:??, June 2018. CODEN ????

ISSN 1942-3454 (print), 1942-3462 (electronic).

Valiant:2014:ERF

[Val14] Paul Valiant. Evolvability of real functions. ACM Transactions on Computation Theory, 6(3):12:1– 12:??, July 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Viderman:2013:LTD

[Vid13] Michael Viderman. Linear-time decoding of regular expander codes. ACM Transactions on Computation Theory, 5(3):10:1– 10:??, August 2013. ISSN 1942-3454 (print), 1942-3462 (electronic). Special issue on innovations in theoretical computer science 2012.

Viola:2016:QMH

[Vio16] Emanuele Viola. Quadratic maps are hard to sample. ACM Transactions on Computation Theory, 8(4):18:1–18:??, July 2016. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Viola:2019:CEP

[Vio19]  Emanuele Viola.  Constant-

error pseudorandomness proofs from hardness require majority. ACM Transactions on Computation Theory, 11(4):19:1– 19:??, September 2019. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/ft_
                                        gateway.cfm?id=3322815.

Viola:2021:AU

[Vio21] Emanuele Viola. AC0 unpredictability. ACM Transactions on Computation Theory, 13(1): 5:1–5:8, March 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3442362.

Volk:2022:PDB

[VK22] Ben Lee Volk and Mrinal Kumar. A polynomial degree bound on equations for non-rigid matrices and small linear circuits. ACM Transactions on Computation Theory, 14(2):6:1–6:??, June 2022. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (elec-

tronic). URL https://dl.acm.
org/doi/10.1145/3543685.

Vlassis:2012:CCS

[VLB12] Nikos Vlassis, Michael L. Littman, and David Barber. On the computational complexity of stochastic controller optimization in POMDPs. ACM Transactions on Computation Theory, 4(4):12:1– 12:??, November 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Volkovich:2016:CAR

[Vol16]  Ilya Volkovich.  Characteriz-

ing arithmetic read-once formulae. ACM Transactions on Computation Theory, 8(1):2:1–2:??, February 2016. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Watson:2012:RWW

[Wat12] Thomas Watson. Relativized worlds without worst-case to average-case reductions for NP. ACM Transactions on Computation Theory, 4(3):8:1–8:??, September 2012. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Watson:2014:ALB

[Wat14] Thomas Watson. Advice lower bounds for the dense model theorem. ACM Transactions on Computation Theory, 7(1):1:1– 1:??, December 2014. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Watson:2018:CCS

[Wat18] Thomas Watson. Communication complexity of statistical distance. ACM Transactions on Computation Theory, 10(1):2:1– 2:??, January 2018. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Watson:2020:QSM

[Wat20a] Thomas Watson. Quadratic simulations of Merlin–Arthur games. ACM Transactions on Computation Theory, 12(2):14:1– 14:11, May 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic). URL https://

                                        dl.acm.org/doi/abs/10.1145/
                                        3389399.

Watson:2020:ZNL

[Wat20b] Thomas Watson. A ZPP NP[1] lifting theorem. ACM Transactions on Computation Theory, 12(4):27:1–27:20, December 2020. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3428673.

Williams:2013:ATP

[Wil13] Ryan Williams. Alternationtrading proofs, linear programming, and lower bounds. ACM Transactions on Computation Theory, 5(2):6:1–6:??, July 2013. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Cai:2021:TLD

[yCG21] Jin yi Cai and Artem Govorov.

On a theorem of Lovász that (·, H) determines the isomorphism type of H. ACM Transactions on Computation Theory, 13 (2):11:1–11:25, June 2021. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

URL https://dl.acm.org/doi/
10.1145/3448641.

Yin:2010:CPP

[Yin10] Yitong Yin. Cell-probe proofs.

ACM Transactions on Computation Theory, 2(1):1:1–1:??, November 2010. CODEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

Zehavi:2023:FCM

[Zeh23] Meirav Zehavi. Forgetfulness can make you faster: an O ∗ (8.097^{k})- time algorithm for weighted 3set k-packing. ACM Transactions on Computation Theory, 15(3–4): 6:1–6:??, December 2023. CO-DEN ???? ISSN 1942-3454 (print), 1942-3462 (electronic).

                                        URL https://dl.acm.org/doi/
                                        10.1145/3599722.